看了下刘汝佳的紫书， 白书。
首先是最大流。怎么找最大流，利用增广路定理
对于当前流求出残量网络，如果残量网络有源点到汇点的通路，也即是增光路，那么流量就可以增大。它的逆命题就是增广路定理——如果当前残量网络不存在增广路，则当前流就是最大流。
下面是 Edmonds-Karp 算法（看了之后才知道做题不用这个……） 代码中的样例：
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define fuck(x) cout<<x<<endl using namespace std; typedef long long ll; const int N = 1e4 + 10; struct Edge { // 存边， int from, to, cap, flow; }; struct EdmondsKarp{ int n, m; vector<Edge> edges; // 边数的两倍 vector<int> G[N]; // 邻接表，G[i][j] 表示节点 i 的第 j 条边在 e 数组中的序号 int a[N]; // 当起点到 i 的可改进量 int p[N]; // 最短路树上 p 的入弧编号，就是路径 void init(int n){ for (int i = 0; i < n; i++){ G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int cap){ // 加边 edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); m = edges.size(); G[from].push_back(m - 2); // 每条边与他的反向边放在一起， G[to].push_back(m - 1); // 这样 i 反向边就是 i^1 } int Maxflow(int s, int t){ int flow = 0; while(1){ memset(a, 0, sizeof(a)); queue<int> Q; Q.push(s); // 放入起点 a[s] = INF; while(!Q.empty()){ int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++){ // 与 x 相连的所有边 Edge &e = edges[G[x][i]]; if(!a[e.to] && e.cap > e.flow){ // 这条边有残量 p[e.to] = G[x][i]; a[e.to] = min(a[x], e.cap - e.flow); Q.push(e.to); } } if(a[t]) break; } if(!a[t]) // 跑 bfs 跑到没有残量网络通路就退出 break; for (int u = t; u != s; u = edges[p[u]].from){ edges[p[u]].flow += a[t]; edges[p[u] ^ 1].flow -= a[t]; } flow += a[t]; } return flow; } }; int main(){ EdmondsKarp kk; kk.init(10); kk.AddEdge(0, 1, 16); kk.AddEdge(0, 2, 13); kk.AddEdge(1, 2, 10); kk.AddEdge(2, 1, 4); kk.AddEdge(1, 3, 12); kk.AddEdge(3, 2, 9); kk.AddEdge(2, 4, 14); kk.AddEdge(4, 3, 7); kk.AddEdge(3, 5, 20); kk.AddEdge(4, 5, 4); fuck(kk.Maxflow(0, 5)); }上面的算法其实比赛的时候是不用的，因为太慢 O(nm^2)。
因为每次增广路有好多条，如果暴力找很费时，所以有了最短增广路算法——每次用 bfs 找出层次图，在图上 dfs 跑阻塞流，这样复杂度为 O(nnm)。而用来跑二分图则更快。下面是 刘汝佳Dinic 代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define fuck(x) cout<<x<<endl using namespace std; typedef long long ll; const int N = 1e4 + 10; struct Edge { // 存边， int from, to, cap, flow; }; struct dinic{ int n, m, s, t; // 结点数， 边数（包括反相弧），源点，汇点 vector<Edge> edges; // 边表，edges[e] 和 edges[e^1] 互为反向弧 vector<int> G[N]; // 邻接表，G[i][j] 表示节点 i 的第 j 条边在 e 数组中的序号 bool vis[N]; // bfs 标记数组 int d[N]; // 从起点到 i 的距离 int cur[N]; // 当前弧下标 void AddEdge(int from, int to, int cap){ edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++){ Edge &e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow){ vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a){ if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++){ // 从上次考虑的弧 Edge &e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0){ e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t){ this->s = s; this->t = t; int flow = 0; while(BFS()){ memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } }; int main(){ dinic kk; kk.AddEdge(0, 1, 10); kk.AddEdge(0, 2, 10); kk.AddEdge(1, 3, 4); kk.AddEdge(1, 4, 8); kk.AddEdge(2, 4, 9); kk.AddEdge(3, 5, 10); kk.AddEdge(4, 5, 10); fuck(kk.Maxflow(0, 5)); // 答案是 14 }所谓当前弧优化就是 DFS 找到一条增广路之后，下次走到某个点就不再走在上次增广路里面的边，减少复杂度。对于前向星就是每次用 cur 数组复制一下 head 数组。
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define ll long long #define fuck(x) cout<<x<<endl const int N = 3e2 + 10; const ll mod = 1e9 + 7; int n, m; int h[N], to[N], ne[N], cap[N], flow[N], idx; // 存图 struct dinic{ int s, t, vis[N], d[N], cur[N]; void add(int u, int v, int c){ // 每次加入弧 和 反向弧 cap[idx] = c, flow[idx] = 0, to[idx] = v, ne[idx] = h[u], h[u] = idx++; cap[idx] = 0, flow[idx] = 0, to[idx] = u, ne[idx] = h[v], h[v] = idx++; } int bfs(){ // BFS 找层次图，直到层次图里面不包括终点 t memset(vis, 0, sizeof(vis)); queue<int> q; q.push(s); d[s] = 0; vis[s] = 1; while(!q.empty()){ int u = q.front(); q.pop(); for(int i = h[u]; ~i; i = ne[i]){ int v = to[i]; if(!vis[v] && cap[i] > flow[i]){ vis[v] = 1; d[v] = d[u] + 1; q.push(v); } } } return vis[t]; } int dfs(int x, int mm){ // 跑阻塞流，加入当前弧优化 if(x == t || mm == 0) return mm; int ans = 0, f; for (int& i = cur[x]; ~i; i = ne[i]){ int v = to[i]; if(d[x] + 1 == d[v] && (f = dfs(v, min(mm, cap[i] - flow[i]))) > 0){ flow[i] += f; flow[i^1] -= f; ans += f; mm -= f; if(mm == 0) break; } } return ans; } int maxflow(int x, int y, int num){ s = x, t = y; int ans = 0; while(bfs()){ for(int i = 0; i <= num; i++) cur[i] = h[i]; ans += dfs(s, INF); } return ans; } }; int main(){ n = 10; dinic kk; idx = 0; // 初始化部分 memset(h, -1, sizeof(h)); kk.add(0, 1, 10); kk.add(0, 2, 10); kk.add(1, 3, 4); kk.add(1, 4, 8); kk.add(2, 4, 9); kk.add(3, 5, 10); kk.add(4, 5, 10); fuck(kk.maxflow(0, 5, 10)); // 答案是 14 }