网络流-SAP算法模板
node 表示当前讨论到的节点； flow 表示该节点被传入/要传出的流量；s, t, ver 分别是起点，终点，节点总数； SAP 函数返回增广路成功增大的流量； dlt 是当前已传出的流量； c 是残量。
1 const int INF = ~0U >> 1; 2 3 int SAP(int node, int flow) 4 { 5 if (node == t) 6 return flow; 7 int p, tmp, dlt = 0; 8 for (p = fst[node]; p; p = nxt[p]) { 9 if (w[p] <= 0 || dis[v[p]] + 1 != dis[node]) 10 continue; 11 tmp = dfs(v[p], min(flow - dlt, c[p])); 12 c[p] -= tmp; 13 c[p + 1] += tmp; 14 if ((dlt += tmp) == flow || dis[s] == ver) 15 return dlt; 16 } 17 if (!--cnt[dis[node]]) 18 dis[s] = ver; 19 ++cnt[++dis[node]]; 20 return dlt; 21 } 22 23 int main() 24 { 25 /* input */ 26 while (dis[s] < ver) 27 ans += SAP(s, INF); 28 printf("%d ", ans); 29 return 0; 30 }