Flow Problem
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 6229 Accepted Submission(s): 2904
Problem Description
Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
Input
The first line of input contains an integer T, denoting the number of test cases.
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
Output
For each test cases, you should output the maximum flow from source 1 to sink 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
题意：题目就是告诉你点和边的数量n和m，然后就是每条边连接的两个点和值，要你求出从1到n的最大流
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define Max 1111
using namespace std;
int n,m,vis[Max],f[Max],v[Max],map[Max][Max];
//vis是标记数组，f是前驱，v是最小值，map是地图
int EK()
{
int i,sum=0,cur,flag;
//sum是记录最大流量，cur是当前点，flag是标记
while(true)
{
//首先找一条最短的从起点到终点的路线切用v记录好流量最小的边
queue<int> q; //用一个队列
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f)); //初始化
q.push(1);
flag=1;
v[1]=1<<30; //起点的最小值初始化无穷大
while(q.size()&&flag) //队列没完且没有找到路线
{
cur=q.front(); //取当前点
q.pop();
for(i=2;i<=n;i++) //遍历所有点
if(!vis[i]&&map[cur][i]) //如果没有标记且有这样的路线
{
q.push(i); //入队
vis[i]=1; //标记已访问
f[i]=cur; //前驱标记
v[i]=min(map[cur][i],v[cur]); //最小值在当前边的值和前驱v的值之间取最小的
if(i==n){flag=0;break;} //如果找到终点就标记有路线且结束
}
}
if(flag)return sum; //如果没有路线存在了就结束
for(i=n;i!=1;i=f[i]) //有路线的话就更新残余网络
{
map[f[i]][i]-=v[n]; //正的减最小值
map[i][f[i]]+=v[n]; //相反的方向就加上来
}
sum+=v[n]; //把新流量加上来
}
}
int main (void)
{
int i,j,k,l,T,cas=1;
scanf("%d",&T);
while(T--&&scanf("%d%d",&n,&m))
{
memset(map,0,sizeof(map));
while(m--&&scanf("%d%d%d",&i,&j,&k))
map[i][j]+=k; //这里有重边，只能叠加
printf("Case %d: %d\n",cas++,EK());
}
return 0;
}