HDU-1532 Drainage Ditches （最大流，EK算法模板）

# include<iostream>
# include<cstdio>
# include<cmath>
# include<string>
# include<vector>
# include<list>
# include<set>
# include<map>
# include<queue>
# include<cstring>
# include<algorithm>
using namespace std;# define LL long long
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CL(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b)const double inf=1e30;
const int INF=1<<30;
const int N=205;struct Edge
{
int fr,to,c,f;
Edge(int _fr,int _to,int _c,int _f):fr(_fr),to(_to),c(_c),f(_f){}
};int n,m;
vector<Edge>e;
vector<int>G[N*2];
int a[N*2],p[N*2];void init()
{
REP(i,0,n) G[i].clear();
e.clear();
}void addEdge(int fr,int to,int cap)
{
e.push_back(Edge(fr,to,cap,0));
e.push_back(Edge(to,fr,0,0));
int len=e.size();
G[fr].push_back(len-2);
G[to].push_back(len-1);
}int maxFlow()
{
int flow=0;
while(1)
{
CL(a,0);
queue<int>q;
q.push(0);
a[0]=INF;
while(!q.empty())
{
int x=q.front();
q.pop();
REP(i,0,G[x].size()){
Edge &edge=e[G[x][i]];
if(!a[edge.to]&&edge.c>edge.f){
p[edge.to]=G[x][i];
a[edge.to]=min(a[x],edge.c-edge.f);
q.push(edge.to);
}
}
if(a[n-1]) break;
}
if(!a[n-1]) break;
for(int u=n-1;u;u=e[p[u]].fr){
e[p[u]].f+=a[n-1];
e[p[u]^1].f-=a[n-1];
}
flow+=a[n-1];
}
return flow;
}int main()
{
int a,b,c;
while(~scanf("%d%d",&m,&n))
{
init();
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
addEdge(a-1,b-1,c);
}
printf("%d\n",maxFlow());
}
return 0;
}