qq11111qqwowo 于 2014.08.19 21:56 提问

#include
#include
#include
using namespace std;
const int maxn = 201;

int edges[maxn][maxn];
int n,m;
int ans;
int father[maxn];
bool visited[maxn];

void ford_fulkerson()
{
ans = 0;
while(1)
{
queue Q;
memset(father,-1,sizeof(father));
memset(visited,0,sizeof(visited));
visited[0] = true;
Q.push(0);
while( !Q.empty())
{
int now = Q.front();
Q.pop();
if(now == m-1)
break;
for(int i = 0; i < m; i++)
{
if(!visited[i] && edges[now][i])
{
father[i] = now;
visited[i] = true;
Q.push(i);
}
}
}
if( !visited[m-1] )
break;
int minimal = 1000000000;
for(int i = m-1; i ; i = father[i])
{
if(minimal > edges[father[i]][i])
minimal = edges[father[i]][i];
}
for(int i = m-1; i ; i = father[i])
{
edges[father[i]][i] -= minimal;
edges[i][father[i]] += minimal;
}
ans += minimal;
}
printf("%d\n",ans);
}
int main()
{
freopen("input.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
int f,t,w;
memset(edges,0,sizeof(edges));
for(int i = 0; i < n; i++)
{
scanf("%d%d%d",&f,&t,&w);
edges[f-1][t-1] += w;
}
ford_fulkerson();
}
return 0;
}
`