[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.2cto.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了...
