#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
struct edge
{
	int y,r,next,op;
}g[405];
int level[205],q[205],h[205];
int n,m,i,ans,a,b,c,tot,vs,vt;

void add(int a,int b,int c)
{
	tot++;
	g[tot].y=b;
	g[tot].r=c;
	g[tot].next=h[a];
	h[a]=tot;
	g[tot].op=tot+1;
	tot++;
	g[tot].y=a;
	g[tot].r=0;
	g[tot].next=h[b];
	h[b]=tot;
	g[tot].op=tot-1;
}

bool bfs()
{
	int i,f,r,tmp,v,u;
	memset(level,0,sizeof(level));
	f=1;
	r=1;
	q[f]=vs;
	level[vs]=1;
	while(f<=r)
	{
		v=q[f];
		tmp=h[v];
		while(tmp!=-1)
		{
			u=g[tmp].y;
			if(g[tmp].r!=0&&level[u]==0)
			{
				level[u]=level[v]+1;
				r++;
				q[r]=u;
				if(u==vt)
				    return true;
			}
			tmp=g[tmp].next;
		}
		f++;
	}
	return false;
}

int dfs(int v,int a)
{
	int ans,flow,tmp,u,value;
	if(v==vt||a==0)
	    return a;
	ans=0;
	tmp=h[v];
	while(tmp!=-1)
	{
		u=g[tmp].y;
		value=g[tmp].r;
		if(level[u]==level[v]+1)
		{
			flow=dfs(u,min(a,value));
			if(flow!=0)
			{
				g[tmp].r-=flow;
				g[g[tmp].op].r+=flow;
				ans+=flow;
				a-=flow;
				if (a==0)
				    break; 
			}
		}
		tmp=g[tmp].next;
	}
	return ans;
}

int main()
{
	memset(h,255,sizeof(h));
	cin>>n>>m;
	tot=0;
	ans=0;
	vs=1;
	vt=m;
	for(i=1;i<=n;i++)
	{
		cin>>a>>b>>c;
		add(a,b,c);
	}
	while(bfs())  
	{
		ans+=dfs(1,2147483647);
	}
	cout<<ans<<endl;
}

• Re:为什么错了 (10) chenyuqi 2016-04-14 20:50:45