POJ 1273 Drainage Ditches 最大流-EdmondsKarp(EK)
[cpp]#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int max(int a,int b){return a<b?b:a;}
int min(int a,int b){return a>b?b:a;}
#define V 205
#define INF 0x3f3f3f3f
int cap[V][V],flow[V][V];// cap是每条边的容量,flow是每条边的流量
int res[V],father[V];//res[]是每个点的剩余流量,father[]是每个点的父亲
int s,t,u,v,f=0; //f是最大流
int m,n,a,b,c;
int EK(int s,int t) //白书EK模板,加点注释大家比较容易理解
{
f=0;
queue<int> q;
memset(flow ,0,sizeof(flow)); //最开始每条边的流量都是0
while(1)
{
memset(res,0,sizeof(res)); //残余流量得变0,一开始所有点都没流入对吧
res[s]=INF; //源点嘛,剩余流量无限是必须的...
q.push(s); //从源点开始进行BFS找增广路
while(!q.empty())
{
u = q.front(); //取队头
q.pop();
for(v=1;v<=n;v++) //遍历所有点,找可行边
{
if(!res[v] && cap[u][v]>flow[u][v]) //该点剩余流量为0 且 容量大于流量,也就是找到了新的结点
{
father[v]=u;//找到新结点,父节点得记录一下吧
q.push(v); //明显新结点要入队列
res[v]=min(res[u],cap[u][v]-flow[u][v]);//如果u的剩余流量能填满uv就填满,不能的话就把u这点的流量全部流向uv
}
}
}
if(res[t]==0) //如果当前已经是最大流,汇点没有残余流量
return f;
for(u=t;u!=s;u=father[u]) //如果还能增广,那么回溯,从汇点往回更新每条走过的边的流量
{
flow[father[u]][u]+=res[t]; //更新正向流量
flow[u][father[u]]-=res[t]; //更新反向流量
} www.zzzyk.com
f+=res[t]; //找到可增广的流量真开心
}
}
int main()
{
while(cin>>m>>n)//万恶多组,贡献一次WA
{
memset(cap,0,sizeof(cap));
memset(flow,0,sizeof(flow));
memset(father,0,sizeof(father));
memset(res,0,sizeof(res));
while(m--)
{
cin>>a>>b>>c;
cap[a][b]+=c; //万恶重边,再贡献一次WA
}
cout<<EK(1,n)<<endl;
}
return 0;
}
有史以来注释最多的EK了...
补充:软件开发 , C++ ,