1.sap
递归版。
View Code #includeusing namespace std;#define MAXN 10000struct Edge{ int v, next, val; Edge( ) { } Edge( int V, int N, int Val): v(V), next(N), val(Val) {} }edge[MAXN];int head[MAXN],size, flow, visit, sum, N, M, ans;int gap[MAXN], h[MAXN];/*sap算法核心:1.dfs搜索增广路2.标号 若存在v(i, j)， 则h[i] = h[j] + 13.gap优化 若出现断层。。则结束 4.更新，正向更新，反向相减 */ void init( ){ for( int i = 0; i < MAXN; i++) { head[i] = -1; } size = 0; }void AddEdge( int u, int v, int val){ edge[size] = Edge(v, head[u], val); head[u] = size++; edge[size] = Edge(u, head[v], 0); head[v] = size++; }int dfs( int x, int flow = 0x7f7f7f7f){ if( x == N ) { return flow; } int v, u, high = N, f, tf = 0; for( v = head[x]; v != -1; v = edge[v].next ) { u = edge[v].v; if( edge[v].val > 0 ) { if( h[x] == h[u] + 1 && (f = dfs(u, min(flow - tf, edge[v].val)))) { edge[v].val -= f; edge[v^1].val += f; tf += f; if( h[1] >= N || tf == flow) return tf; } high = min(high, h[u]); } } if( tf == 0 ) { gap[h[x]]--; if( gap[h[x]] == 0 ) h[1] = N; h[x] = high + 1; gap[h[x]]++; } return tf; }void solve( ){ gap[0] = N; memset(h, 0, sizeof(h)); sum = 0; while( h[1] < N ) sum += dfs( 1 ); printf("Case %d: %d\n",++ans, sum); }int main( ){ int a, b, c, T; ans = 0; scanf("%d",&T); while( T-- ) { scanf("%d%d",&N, &M); init( ); for( int i = 1; i <= M; i++) { scanf("%d%d%d",&a, &b, &c); AddEdge(a, b, c); } solve( ); } return 0; }
2. sap非递归版
View Code #include#include using namespace std;#define MAXN 10000struct Edge{ int v, next, val; Edge( ) { } Edge( int V, int N, int Val): v(V), next(N), val(Val) { }}edge[MAXN];int head[MAXN], cur[MAXN], gap[MAXN], h[MAXN], path[MAXN], size, N, M, ans;queue q;void init( ){ for( int i = 0; i < MAXN; i++) head[i] = -1; size = 0; }void AddEdge( int u, int v, int val){ edge[size] = Edge(v, head[u],val); head[u] = size++; edge[size] = Edge(u, head[v], 0); head[v] = size++; }void bfs( ){ q.push( N ); while( !q.empty() ) { int x = q.front(); q.pop( ); for( int u = head[x]; u != -1; u = edge[u].next) { int v = edge[u].v; if( h[v] == 0 && edge[u^1].val > 0) { gap[0]--; h[v] = h[u] + 1; gap[h[v]]++; q.push( v ); } } } }void sap( ){ memset(h, 0, sizeof(h)); memset(gap, 0, sizeof(gap)); for( int i = 0; i < MAXN; i++) { cur[i] = head[i]; path[i] = 0; } gap[0] = N; int u = 1, v, flow = 0x7f7f7f7f, high, sum = 0; path[u] = u = 1; while( h[1] < N ) { int f = 0; for( int &x = cur[u]; x != -1; x = edge[x].next ) { if( edge[x].val > 0 ) { int v = edge[x].v; int w = edge[x].val; if( h[u] == h[v] + 1 ) { path[v] = u; u = v; flow = min(flow, edge[x].val); f = 1; if( v == N ) { sum += flow; for( u = path[v] ; v != 1; v = u, u = path[u]) { edge[cur[u]].val -= flow; edge[cur[u]^1].val += flow; } flow = 0x7f7f7f7f; } break; } } } if( f ) continue; high = N; for( int t = head[u]; t != -1; t = edge[t].next ) { int w = edge[t].val; int v = edge[t].v; if( w > 0 ) { if( h[v] < high ) { high = h[v]; cur[u] = t; } } } gap[h[u]]--; if( gap[h[u]] == 0 ) h[1] = N; h[u] = high + 1; gap[h[u]]++; u = path[u]; } printf("Case %d: %d\n",ans++,sum);}int main( ){ int a,b,c,T; scanf("%d", &T); ans = 1; while(T--) { scanf("%d%d", &N, &M); init( ); for( int i = 0; i < M; i++) { scanf("%d%d%d",&a, &b,&c); AddEdge(a,b,c); } sap(); } return 0;}
3.dinic非递归版本
View Code #include#include using namespace std;#define MAXN 10610struct Edge{ int v, next, val; Edge( ) { } Edge(int V,int N, int Val): v(V), next(N), val(Val) { }}edge[MAXN];queue q;int head[MAXN], h[MAXN], size, N, M, ans, cur[MAXN];int Q[106000];void init( ){ for( int i = 0; i < MAXN; i++) head[i] = -1; size = 0; }void AddEdge( int u, int v, int val){ edge[size] = Edge(v, head[u], val); head[u] = size++; edge[size] = Edge(u, head[v], 0); head[v] = size++; }int bfs( ){ memset( h, -1, sizeof(h)); q.push( 1 ); h[1] = 0; while( !q.empty()) { int x = q.front(); q.pop( ); for( int e = head[x]; e != -1; e = edge[e].next) { int w = edge[e].val; int v = edge[e].v; if( w > 0 && h[v] == -1) { h[v] = h[x] + 1; q.push( v ); } } } return h[N] != -1; }int dfs( ){ int e, u, v, w, p, i, sum = 0, f = 0; for( int i = 0; i <= N + 100; i++) cur[i] = head[i]; p = 1; Q[p] = 1; while( p ) { int x = Q[p]; if( x == N ) { int flow = 0x7fffffff; for( i = 1; i < p; i++) { x = Q[i]; e = cur[x]; if( edge[e].val < flow ) flow = edge[e].val; } int mid; for( i = 1; i < p; i++) { x = Q[i]; e = cur[x]; if( edge[e].val == flow ) mid = i; edge[e].val -= flow; edge[e^1].val += flow; } p = mid; sum += flow; continue; } for(e = cur[x]; e != -1; e = edge[e].next) { v = edge[e].v; w = edge[e].val; if( h[v] == h[x] + 1 && w > 0 ) { Q[++p] = v; break; } } cur[x] = e; if( e == -1 ) { p--; cur[Q[p]] = edge[cur[Q[p]]].next; } } return sum;}void solve( ){ int sum = 0; while( bfs( ) ) sum += dfs( ); printf("Case %d: %d\n",ans++,sum);}int main( ){ int a, b, c, T; scanf("%d",&T); ans = 1; while(T--) { scanf("%d%d",&N, &M); init( ); for( int i = 1; i <= M; i++) { scanf("%d%d%d",&a, &b, &c); AddEdge(a, b, c); } solve( ); } return 0; }
4.dinic递归版
View Code #include#include using namespace std;#define MAXN 1010struct Edge{ int v, next, val; Edge( ) { } Edge(int V,int N, int Val): v(V), next(N), val(Val) { }}edge[MAXN];queue q;int head[MAXN], h[MAXN], size, N, M, flow, visit, ans;void init( ){ for( int i = 0; i < MAXN; i++) head[i] = -1; size = 0; }void AddEdge( int u, int v, int val){ edge[size] = Edge(v, head[u], val); head[u] = size++; edge[size] = Edge(u, head[v], 0); head[v] = size++; }int bfs( ){ memset( h, -1, sizeof(h)); q.push( N ); h[N] = 0; while( !q.empty()) { int x = q.front(); q.pop( ); for( int e = head[x]; e != -1; e = edge[e].next) { int w = edge[e^1].val; int v = edge[e].v; if( w > 0 && h[v] == -1) { //printf("x = %d v = %d w = %d\n", x, v, w); h[v] = h[x] + 1; q.push( v ); } } } return h[1] != -1; }int dfs(int x, int flow = 0x7f7f7f7f){ if( x == N ) { return flow; } int e, tf = 0, f; for(e = head[x]; e != -1; e = edge[e].next) { int v = edge[e].v; int w = edge[e].val; if( h[x] == h[v] + 1 && w > 0 && (f = dfs(v, min(flow - tf, w))) ) { edge[e].val -= f; edge[e^1].val += f; tf += f; } } if( tf == 0) h[x] = -1; return tf;}void solve( ){ int sum = 0; while( bfs( ) ) sum += dfs(1); printf("Case %d: %d\n",ans++,sum);}int main( ){ int a, b, c, T; scanf("%d",&T); ans = 1; while(T--) { scanf("%d%d",&N, &M); init( ); for( int i = 1; i <= M; i++) { scanf("%d%d%d",&a, &b, &c); AddEdge(a, b, c); } solve( ); } return 0; }