给定多张图,求从1到n的最大流
Input
第一行数据组数 后面每一组数据第一行n,m表示顶点数、边数(n<=15,m<=1000) 后面m行给出每条有向边的信息
Output
对每一组数据,输出从1到n的最大流
Sample Input
2 3 2 1 2 1 2 3 1 3 3 1 2 1 2 3 1 1 3 1
Sample Output
Case 1: 1 Case 2: 2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1005;
int n,s,t;
int e[20][20],flag[20],pre[20];
bool bfs() //寻找一条由起点到终点的增广路
{
memset(flag,0,sizeof(flag));
memset(pre,-1,sizeof(pre));
queue<int> q;
q.push(s);
flag[s]=1,pre[s]=s;
int now;
while(!q.empty())
{
now=q.front();
q.pop();
for(int i=1; i<=n; i++)
{
if(!flag[i]&&e[now][i]>0)
{
flag[i]=1;
pre[i]=now;
q.push(i);
if(i==t)
return 1;
}
}
}
return 0;
}
int Edmonds_Karp()
{
int max_flow=0,mi;
while(bfs())
{
mi=maxn;
for(int i=t; i!=s; i=pre[i])
{
mi=min(mi,e[pre[i]][i]);
}
for(int i=t; i!=s; i=pre[i])
{
e[pre[i]][i]-=mi;
e[i][pre[i]]+=mi;
}
max_flow+=mi;
}
return max_flow;
}
int main()
{
int T,cnt=1;
cin>>T;
while(T--)
{
int m;
cin>>n>>m;
memset(e,0,sizeof(e));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
e[a][b]+=c; //可能有重边
}
s=1,t=n;
printf("Case %d: %d\n",cnt++,Edmonds_Karp());
}
return 0;
}