题目地址：http://poj.org/problem?id=1273
裸的网络流
Dinic算法如下：
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=300;
const int INF=(1<<30);
int m,n; //m为顶点数，n为边数
int G[maxn][maxn];
bool vis[maxn];
int layer[maxn]; //记录层次
bool getLayer() //分层
{queue<int> Q;memset(layer,0,sizeof(layer));layer[1]=1;Q.push(1);while(!Q.empty()){int u=Q.front(); Q.pop();for(int v=1;v<=m;v++)if(G[u][v]>0&&!layer[v]){layer[v]=layer[u]+1;if(v==m) return true; //一旦到终点m就不必分层了 Q.push(v);} }return false;
}
int Dinic()
{int MaxFlow=0;while(getLayer()){deque<int> DQ; //保存路径 memset(vis,0,sizeof(vis));vis[1]=1;DQ.push_back(1);while(!DQ.empty()){int u=DQ.back();if(u==m) //找到增广路径了，便找出最小流，更新网络流，添加反向边 {int MinFlow=INF; //最小流 int pMin; //最小流的上一个节点位置 for(int i=1;i<DQ.size();i++){int u=DQ[i-1];int v=DQ[i];if(G[u][v]>0&&MinFlow>G[u][v]) //找出最小流 {MinFlow=G[u][v];pMin=u; } }MaxFlow+=MinFlow; //累加到最大流 for(int i=1;i<DQ.size();i++){int u=DQ[i-1];int v=DQ[i];G[u][v]-=MinFlow; //更新最小流 G[v][u]+=MinFlow; //添加反向边 }while(!DQ.empty()&&DQ.back()!=pMin){ //退栈到PMin，回溯继续找增广路径 vis[DQ.back()]=0;DQ.pop_back();}continue;}int ok=0;for(int v=1;v<=m;v++)if(G[u][v]>0&&!vis[v]&&layer[v]==layer[u]+1) //只能走到下一层 {ok=1;vis[v]=1;DQ.push_back(v);break; }if(!ok) DQ.pop_back(); //不能走就pop，换一条路走 } }return MaxFlow;
}
int main()
{while(cin>>n>>m) //从1~m的最大流 {int u,v,w;memset(G,0,sizeof(G));for(int i=0;i<n;i++){cin>>u>>v>>w; //u-->v 上限是w G[u][v]+=w; //可能有多条边 }cout<<Dinic()<<endl; }return 0;
} Edmonds-Karp算法如下：
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=300;
const int INF=(1<<30);
int m,n;
int G[maxn][maxn];
int prev[maxn]; //记录前驱节点，记录增广路径
bool vis[maxn];
int Augment() //增广
{queue<int> Q;bool isFound=false; //标记是否找到了增广路 memset(vis,false,sizeof(vis));memset(prev,0,sizeof(prev));Q.push(1);vis[1]=true;while(!Q.empty()){int u=Q.front(); Q.pop();if(u==m) { //找到增广路径了 isFound=true;break;}for(int v=1;v<=m;v++)if(G[u][v]>0&&!vis[v]){prev[v]=u;vis[v]=1;Q.push(v); }}if(!isFound) return 0; //无路可走 int MinFlow=INF; int u=m;while(prev[u]){ //计算途中最小流 MinFlow=min(MinFlow,G[prev[u]][u]);u=prev[u];}u=m;while(prev[u]){G[prev[u]][u]-=MinFlow; //更新途径路的流量 G[u][prev[u]]+=MinFlow; //加上反向边 u=prev[u];}return MinFlow;
}
int main()
{while(cin>>n>>m){int u,v,w;memset(G,0,sizeof(G));for(int i=0;i<n;i++){cin>>u>>v>>w; //u-->v 上限是w G[u][v]+=w; //可能有多条边 }int MaxFlow=0;int aug;while(aug=Augment())MaxFlow+=aug; //加上每次增广的流 cout<<MaxFlow<<endl; }return 0;
}