题目描述
Lily runs a repairing company that services the $Q$ blocks in the city. One day the company receives $M$ repair tasks, the $i$-th of which occurs in block $p_i$, has a deadline $t_i$ on any repairman’s arrival, which is also its starting time, and takes a single repairman $d_i$ time to finish. Repairmen work alone on all tasks and must finish one task before moving on to another. With a map of the city in hand, Lily want to know the minimum number of repairmen that have to be assign to this day’s tasks.
题意概述
有$Q$个街道和$M$个任务。给出两两街道之间的距离以及每个任务的地点$p_i$、开始时间$t_i$和花费时间$d_i$。问至少需要多少个工人才能完成所有任务。工人开始时可以在任意街道,一个工人只能同时做一个任务。
数据范围:$1 \le Q \le 20, \; 1 \le M \le 200$。
算法分析
首先用Floyd求出任意两点之间的距离,用$dist_{i, j}$表示。对于两个任务$i, j$,若$t_i+d_i+dist_{p_i, p_j} \le t_j$,那么做第$i$个任务的工人可以继续做第$j$个任务。显然,任务之间构成了一张有向无环图,问题转化为最小覆盖问题。将图中每个点$u$拆成$u_0, u_1$两个点。若原图中有一条边$(u, v)$,则在新图中连边$(u_0, v_1)$。答案就是$M$减去新图的最大匹配数。
代码
#include <cstdio> #include <cstring> int min(int a, int b) { return a < b ? a : b; } static const int Q = 25; static const int M = 405; int mp[Q][Q], p[M], t[M], d[M]; int nume, h[M]; struct Edge { int v, f, nxt; } e[M * M << 1]; void add_edge(int u, int v, int f) { e[++ nume] = (Edge) { v, f, h[u] }, h[u] = nume; e[++ nume] = (Edge) { u, 0, h[v] }, h[v] = nume; } namespace flow { int S, T, g[M], dist[M], que[M], gap[M]; bool bfs() { memcpy(g, h, sizeof h); memset(dist, 0x3f, sizeof dist), memset(gap, 0, sizeof gap); int qb = 0, qe = 1; dist[T] = 0, que[0] = T, ++ gap[0]; while (qb < qe) { int u = que[qb ++]; for (int i = g[u]; i; i = e[i].nxt) if (e[i ^ 1].f && dist[e[i].v] > dist[u] + 1) dist[e[i].v] = dist[u] + 1, que[qe ++] = e[i].v, ++ gap[dist[e[i].v]]; } return dist[S] < 1e9; } int dfs(int t, int low) { if (t == T) return low; int used = 0; for (int &i = g[t]; i; i = e[i].nxt) if (e[i].f && dist[e[i].v] == dist[t] - 1) { int flow = dfs(e[i].v, min(e[i].f, low - used)); if (flow) e[i].f -= flow, e[i ^ 1].f += flow, used += flow; if (used == low || dist[S] > T) return used; } if (! -- gap[dist[t]]) dist[S] = T + 1; else ++ gap[++ dist[t]], g[t] = h[t]; return used; } int maxflow() { bfs(); int flow = 0; while (dist[S] <= T) flow += dfs(S, 1e9); return flow; } } int main() { int q, m; while (scanf("%d%d", &q, &m), q) { nume = 1, memset(h, 0, sizeof h); flow :: S = m << 1, flow :: T = (m << 1) + 1; for (int i = 0; i < q; ++ i) for (int j = 0; j < q; ++ j) scanf("%d", &mp[i][j]); for (int i = 0; i < q; ++ i) for (int j = 0; j < q; ++ j) if (! ~ mp[i][j]) mp[i][j] = 1e9; for (int k = 0; k < q; ++ k) for (int i = 0; i < q; ++ i) for (int j = 0; j < q; ++ j) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]); for (int i = 0; i < m; ++ i) scanf("%d%d%d", &p[i], &t[i], &d[i]), -- p[i]; for (int i = 0; i < m; ++ i) for (int j = 0; j < m; ++ j) if (i != j && t[i] + d[i] + mp[p[i]][p[j]] <= t[j]) add_edge(i, j + m, 1); for (int i = 0; i < m; ++ i) add_edge(flow :: S, i, 1), add_edge(i + m, flow :: T, 1); printf("%d\n", m - flow :: maxflow()); } return 0; }