前言
如果有人不会网络流，那么安利一下我
关于网络流，我多久没有碰这个算法了... 今天旁边的巨佬@Chhokmah在做网络流，于是我也顺便做了一下。 然后意外发现自己介绍Dinic的博客浏览1000+了，把我吓了一跳。 这确实是一道网络流好题。题解
这道题目难点主要是构图。
这道题的构图一开始很容易想到建一个超级源点连房间，房间连人，人连菜，菜连汇点。 最后跑一遍最大流求出答案。 然后交了一下直接WA 60。 仔细一想发现有一个问题 比如下面这组数据1 3 31 1 11 1 1
答案应该是1，但当前的算法输出是三，算法的错误是中间的人被重复利用了。
于是我们想到了一个技巧，拆点。 把一个人拆成两个点，中间连接一条流量为1的边，这样保证了一个人最多只会被利用一次。 于是重新构图： 建一个超级源点连房间，房间连人1，人1连人2，人2连菜，菜连汇点。 注:其中人1和人2是同一个人。 然后接着跑一遍网络流求出答案即可。代码
#include#include #include #include using namespace std;const long long MAX = (1ll << 62);int read(){ int x = 0; int zf = 1; char ch = ' '; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}struct Edge{ int to, next; long long dis;} edges[210000];int cur[10010], head[10010], edge_num = -1;void addEdge2(int from, int to, long long dis){ edges[++edge_num].to = to; edges[edge_num].dis = dis; edges[edge_num].next = head[from]; head[from] = edge_num;}void addEdge(int from, int to, long long dis){ addEdge2(from, to, dis), addEdge2(to, from, 0);}int d[10010];int s, t;long long DFS(int u, long long flow){ if (u == t) return flow; long long _flow = 0, __flow; for (int& c_e = cur[u]; c_e != -1; c_e = edges[c_e].next){ int v = edges[c_e].to; if (d[v] == d[u] + 1 && edges[c_e].dis > 0){ __flow = DFS(v, min(flow, edges[c_e].dis)); flow -= __flow; edges[c_e].dis -= __flow; _flow += __flow; edges[c_e ^ 1].dis += __flow; if (!flow) break; } } if (!_flow) d[u] = -1; return _flow;}bool BFS(){ memset(d, -1, sizeof(d)); queue que; que.push(s); d[s] = 0; int u, _new; while (!que.empty()){ u = que.front(), que.pop(); for (int c_e = head[u]; c_e != -1; c_e = edges[c_e].next){ _new = edges[c_e].to; if (d[_new] == -1 && edges[c_e].dis > 0){ d[_new] = d[u] + 1; que.push(_new); } } } return (d[t] != -1);}int n;void dinic(){ long long max_flow = 0; while (BFS()){ for (int i = 0; i <= n; ++i) cur[i] = head[i]; max_flow += DFS(s, MAX); } printf("%lld", max_flow);}int main(){ memset(head, -1, sizeof(head)); int N = read(), p = read(), q = read(); s = 0; for (int j = 1; j <= p; ++j) addEdge(s, j, 1); for (int i = 1; i <= N; ++i) for (int j = 1; j <= p; ++j) if (read() == 1) addEdge(j, p + q + i, 1); for (int i = 1; i <= N; ++i) addEdge(p + q + i, p + q + N + i, 1); for (int i = 1; i <= N; ++i) for (int j = 1; j <= q; ++j) if (read() == 1) addEdge(p + q + N + i, p + j, 1); n = t = p + q + N * 2 + 1; for (int j = 1; j <= q; ++j) addEdge(p + j, t, 1); dinic(); return 0;}