关键割边
??? 关键割边就是增加某条边的容量，使得网络的最大流增加。
??? 步骤：
??? 1. 求最大流，得到残余网络。
??? 2. 在残余图上从s点出发dfs，得到割边(a,b)。
??? 3. 从t点出发反向dfs，得到所有能到达t的点。
??? 4. 对于某条割边(a,b)，若b能到达t，则该边为关键割边。(因为从s到t的路径上只有这一条割边，增加这条割边，肯定可以增加流量)。
?
例：POJ3024
??? 题意：找关键割边数量。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int INF = 0x7fffffff;const int maxv = 505;const int maxe = 5005*2;int n,m;int col[maxv];bool vis[maxv];//struct Edge{ int v; int next; int flow;};Edge e[maxe];int head[maxv],edgeNum;int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];void addEdge(int a,int b,int c){ e[edgeNum].v = b; e[edgeNum].flow = c; e[edgeNum].next = head[a]; head[a] = edgeNum++; e[edgeNum].v = a; e[edgeNum].flow = 0; e[edgeNum].next = head[b]; head[b] = edgeNum++;}void Init(){ edgeNum = 0; memset(head,-1,sizeof(head)); memset(d,0,sizeof(d));}int sap(int s,int t,int n) //源点，汇点，结点总数{ int i,x,y; int f,ans = 0; for(i = 0; i < n; i++) now[i] = head[i]; vh[0] = n; x = s; while(d[s] < n) { for(i = now[x]; i != -1; i = e[i].next) if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x]) break; if(i != -1) { now[x] = preh[y] = i; pre[y] = x; if((x=y) == t) { for(f = INF,i=t; i != s; i = pre[i]) if(e[preh[i]].flow < f) f = e[preh[i]].flow; ans += f; do { e[preh[x]].flow -= f; e[preh[x]^1].flow += f; x = pre[x]; }while(x!=s); } } else { if(!--vh[d[x]]) break; d[x] = n; for(i=now[x]=head[x]; i != -1; i = e[i].next) { if(e[i].flow > 0 && d[x] > d[e[i].v] + 1) { now[x] = i; d[x] = d[e[i].v] + 1; } } ++vh[d[x]]; if(x != s) x = pre[x]; } } return ans;}void minmGe(int x){ col[x] = 1; for(int i = head[x]; i != -1; i = e[i].next) { int to = e[i].v; if(e[i].flow > 0 && !col[to]) minmGe(to); }}//void dfs(int now){ vis[now] = true; for(int i = head[now]; i != -1; i = e[i].next) { if(i%2==0) continue; int to = e[i].v; if(e[i^1].flow>0&&!vis[to]) dfs(to); }}int main(){ int i,j; int from,to,c; Init(); memset(col,0,sizeof(col)); memset(vis,0,sizeof(vis)); scanf("%d %d",&n,&m); for(i = 0; i < m; i++) { scanf("%d %d %d",&from,&to,&c); addEdge(from,to,c); } sap(0,n-1,n); minmGe(0); int result = 0; dfs(n-1); for(i = 0; i < n; i++) { if(!col[i]) continue; for(j = head[i]; j != -1; j = e[j].next) { int to = e[j].v; if(j%2==0 && col[to]==0 && vis[to]) result++; } } printf("%d\n",result++); return 0;}?
?
?
?