残留网络

流

终于看懂了0 0


#include <cstdio>
#include <cstring>
#define N 201

int n,m;
int f[N][N],c[N][N];
bool vis[N];

const int inf = 10000010;

int inline min(int x,int y){return x>y?y:x;}

bool dfs(int s,int t,int &flow)
{
	int i,j,cf;
	vis[s]=true;
	if(s==t)return true;
	for(i=1;i<=m;++i)
	{
		if(vis[i])continue;
		if(c[s][i]>0)
		{
			j = flow;
			flow=min(flow,c[s][i]);
			if(dfs(i,t,flow))
			{
				f[s][i]+=flow;
				c[i][s]+=flow;
				c[s][i]-=flow;
				return true;
			}
			flow = j;
		}
	}
	return false;
}

int find(int s=1,int t=m)
{
	int flow = inf;
	memset(vis,0,sizeof(vis));
	vis[s]=true;
	dfs(s,t,flow);
	if(flow>=inf)return 0;
	else return flow;
}

int max_flow()
{
	int ret=0,i;
	memset(f,0,sizeof(f));
	while(find());
	for(i=1;i<=m;++i)
		ret+=f[1][i];
	return ret;
}

int main(void)
{
	int i,x,y,z;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(c,0,sizeof(c));
		for(i=0;i<n;++i)
		{
			scanf("%d%d%d",&x,&y,&z);
			c[x][y]+=z;
		}
		printf("%d\n",max_flow());
	}
	return 0;
}