Flow Problem
Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 14791 Accepted Submission(s): 6960
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)
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
分析
裸的 Edmods_karp算法
Edmods_Karp 算法其实就是 不停BFS(找源点与汇点的路径)+不停维护剩余网络，直到找不到路了,就求得Max_flow
注意 map[t1] [ t2 ] +=t3; 重边时 ，容量可以叠加，想象成从t1到t2有多条水管。
#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define N 20
int map[N][N]; // 假设我们这里有N个节点，这里存的边是(i->j)的容量上限，有向边
// 没有边时，容量就是0
int queue[N]; //用来跑BFS
int visit[N]; // 记录点是否被访问过
int last[N]; // 记录BFS来的上一个点是谁
int min[N]; // 记录BFS来到这个点的一路上容量最小的边是多少
void residual(int tar);
int BFS(int src,int tar,int n);
int edmonds_karp(int src,int tar,int n){ // src源点 , tar 汇点
int max_flow = 0;
int new_flow=0;
do{
new_flow = BFS(src,tar,n);
max_flow += new_flow;
} while( new_flow !=0);
return max_flow;
}
int BFS(int src,int tar,int n){
memset(visit,0,sizeof(visit));
// src必要的init
min[src] =INF;
last[src]= -1;
visit[src]=1;
//将 src 放入 queue;
queue[0] =src;
int qhead,qtail=1;
for( qhead =0; qhead < qtail;qhead++){
if(queue[qhead] == tar) break;
int cur=queue[qhead];
for(int i= 0; i<n ;i++){
if( !visit[i] && map[cur][i] !=0){
queue[qtail++] =i;
min[i] =(min[cur] < map[cur][i] ? min[cur]: map[cur][i]);
last[i]=cur;
visit[i] =1;
}
}
}
if( qhead == qtail ) return 0;
residual(tar);
return min[tar];
}
void residual(int tar){
int flow=min[tar];
int cur=tar;
while(last[cur] != -1){
map[last[cur]][cur] -= flow;
map[cur] [last[cur]] +=flow;
cur=last[cur];
}
}
using namespace std;
int main(){
int T;
cin>>T;
for(int cas=1;cas <=T;cas++){
int n,m;
cin>>n>>m;
memset(map,0,sizeof(map));
int t1,t2,t3;
for(int i=0;i<m;i++){
cin>>t1>>t2>>t3;
map[t1-1][t2-1] +=t3;
}
cout<<"Case "<<cas<<": ";
cout<<edmonds_karp(0,n-1,n)<<endl;
}
return 0;
}