#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
using namespace std;
#define INF 1000000000
#define MAXN 1000
int a[MAXN];
int cap[MAXN][MAXN],flow[MAXN][MAXN],p[MAXN];
queue<int>q;
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(cap,0,sizeof(cap));
int a1,b,c;
for(int i=1;i<=n;i++)
{
cin>>a1>>b>>c;
cap[a1][b]+=c;
}
int t=m;
memset(flow,0,sizeof(flow));
int f=0;
int s=1;
while(1)
{
memset(a,0,sizeof(a));
a[s]=INF;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=1;v<=m;v++)
if(!a[v]&&cap[u][v]>flow[u][v])
{
p[v]=u;
q.push(v);
a[v]=a[u]<cap[u][v]-flow[u][v]?a[u]:cap[u][v]-flow[u][v];
}
}
if(a[t]==0)
break;
for(int u=t;u!=s;u=p[u])
{
flow[p[u]][u]+=a[t];
flow[u][p[u]]-=a[t];
}
f+=a[t];
}
printf("%d\n",f);
}
return 0;
}
转载于:https://www.cnblogs.com/cyiner/archive/2011/07/20/2112225.html
相关资源：JAVA上百实例源码以及开源项目
