POJ 1273 Drainage Ditches 网络流算法 .

题目地址：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; }