标记法-来源<图论算法理论、实现及应用-王桂平>
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; struct ArcType { int c,f; ///容量,流量 }; ArcType Edge[maxn][maxn]; ///弧矩阵 int n,m; ///顶点个数和弧数 int flag[maxn]; ///这里表明顶点的状态,-1-未标号,0-已标号未检查,1-已标号已检查 int prev[maxn]; ///标号的第一个分量,表明前一个顶点,便于回溯. int alpha[maxn]; ///标号的第二个分量,表示改进量 queue<int> qu; ///队列 - 进行BFS void ford() { while(1) { memset(flag,-1,sizeof(flag));memset(prev,-1,sizeof(prev));memset(alpha,-1,sizeof(alpha)); flag[0] = 0;prev[0] = 0;alpha[0] = INF; ///源点为已标号未检查顶点 while(!qu.empty()) qu.pop(); qu.push(0); while(!qu.empty() && flag[n-1] == -1 ) ///如果队列不为空且终点还没有标记 { int v = qu.front();qu.pop(); for(int i=0;i<n;i++) if(flag[i] == -1){ /// 检查和顶点v正向和反向邻接的顶点.没有标号 /// '正向'且'未满' if(Edge[v][i].c < INF && Edge[v][i].f < Edge[v][i].c) { flag[i] = 0;prev[i] = v; alpha[i] = min(alpha[v],Edge[v][i].c-Edge[v][i].f); qu.push(i); } /// '反向'且有流量 else if(Edge[i][v].c < INF && Edge[i][v].f > 0) { flag[i] = 0;prev[i] = -v; alpha[i] = min(alpha[v],Edge[i][v].f); qu.push(i); } } flag[v] = 1; ///表示顶v已经检查了 } /// 当汇点没有被标记,或者汇点的调整量为0时,应当退出while循环 if(flag[n-1]==-1 || alpha[n-1] == 0) break; int k1=n-1,k2=abs(prev[k1]); int a=alpha[n-1]; /// 可改进量 while(1) { if(Edge[k2][k1].f<INF) /// 正向 Edge[k2][k1].f+=a; else Edge[k1][k2].f-=a; if(k2==0) break; k1=k2;k2=abs(prev[k2]); } } int maxflow=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==0 && Edge[i][j].f<INF) ///求源点的最大流 maxflow += Edge[i][j].f; if(Edge[i][j].f < INF) printf("%d->%d:%d\n",i,j,Edge[i][j].f); } } printf("maxFlow:%d\n",maxflow); } int main() { int u,v,c,f; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) ///初始化 for(int j=0;j<n;j++) Edge[i][j].c=Edge[i][j].f=INF; for(int i=0;i<m;i++){ ///读入每一条边 scanf("%d%d%d%d",&u,&v,&c,&f); Edge[u][v].c=c;Edge[u][v].f=f; } ford(); return 0; }来源:<算法竞赛入门经典>
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxn = 1010; const int INF = 0x3f3f3f3f; typedef struct node { int from,to,cap,flow; node(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} }Edge; typedef struct EdmondsKarp { int n,m; vector<Edge> edges; vector<int> G[maxn]; int a[maxn]; int p[maxn]; ///初始化 void init(int n) { for(int i=0;i<n;i++) G[i].clear(); edges.clear(); } ///加边 void AddEdge(int from,int to,int cap,int ff) { 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); ///放入正向弧,弧头为from. G[to].push_back(m-1); ///放入反向弧,弧头为to, } ///计算最大流 int Maxflow(int s,int t) { int flow = 0; while(true) { memset(a,0,sizeof(a)); queue<int> qu; qu.push(s); a[s] = INF; while(!qu.empty()) { int x = qu.front();qu.pop(); for(int i=0;i<G[x].size();i++) { Edge& e = edges[G[x][i]]; /// e.cap > e.flow 也能用来更新反向边.因为 [e].flow = -e.flow (反向弧的流量是其正向弧的负数) if(!a[e.to] && e.cap > e.flow) { ///a[]既是可改进量数组,也能代表节点有没有被访问, p[e.to] = G[x][i]; ///p记录的是边的序号 a[e.to] = min(a[x],e.cap-e.flow); qu.push(e.to); } } if(a[t]) break; } if(!a[t]) break; ///如果到达不了t或者a[t]的可改进量为0,说明已经找到了最大流 /// 用a[t]作为改进量更新增广路. for(int u=t;u!=s;u=edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; ///因为每条弧和对应的反向弧保存在一起,0和1是方向边,同理2,3.... ///于是[x^1]就是[x]的反向边.这里的反向弧的流量是正向弧的相反数(负数). } flow += a[t]; } return flow; } }Ed; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { Ed solve; solve.init(n); for(int i=0;i<m;i++) { int u,v,c,f; scanf("%d%d%d%d",&u,&v,&c,&f); solve.AddEdge(u,v,c,f); } int ans = solve.Maxflow(0,n-1); printf("maxFlow:%d\n",ans); } return 0; }