ISAP求最大流，敲了一发板子，无压行，教程略去。转载请随意。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; ; const int inf = 0x33333333; struct edge { int to, rev, cap; }; int n; vector<edge> G[maxn]; void add_edge(int u, int v, int cap) { G[u].push_back((edge){v, (int)G[v].size(), cap}); G[v].push_back((edge){u, (, }); } int isap(int s, int t) { //init static int h[maxn]; //距离标号 static int cnt[maxn]; //距离标号计数 static int cur[maxn]; //当前弧 static int pv[maxn]; //上一个顶点 static int pe[maxn]; //上一条弧 memset(h, , sizeof h); memset(cnt, , sizeof cnt); cnt[] = n; memset(cur, , sizeof cur); //solve int u = s; ; while(true) { if(u == t) { //augment int newflow = inf; for(int x = t; x != s; x = pv[x]) { edge &e = G[pv[x]][pe[x]]; newflow = min(newflow, e.cap); } flow += newflow; for(int x = t; x != s; x = pv[x]) { edge &e = G[pv[x]][pe[x]]; e.cap -= newflow; G[x][e.rev].cap += newflow; } u = s; } bool did = false; for(int &i = cur[u]; i < (int)G[u].size(); ++i) { edge &e = G[u][i]; && h[u] == h[e.to] + ) { //advance did = true; pv[e.to] = u; pe[e.to] = i; u = e.to; break; } } if(!did) { //retreat ; ; i < (int)G[u].size(); ++i) { edge &e = G[u][i]; ) { newh = min(newh, h[e.to] + ); } } ) { //gap break; } ++cnt[h[u] = newh]; if(u != s) { u = pv[u]; } } } return flow; } int main(void) { int m, source, sink; scanf("%d%d%d%d", &n, &m, &source, &sink), --source, --sink; ; i < m; ++i) { int from, to, cap; scanf("%d%d%d", &from, &to, &cap), --from, --to; add_edge(from, to, cap); } printf("%d\n", isap(source, sink)); ; }
