Flow Problem

Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 12860    Accepted Submission(s): 6128

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

 

 

Author

HyperHexagon

 

 

Source

 

 

Recommend

zhengfeng   |   We have carefully selected several similar problems for you:            

 

同hdu 1532，也是最大流模板题，不过先输入水沟的顶点数，再输入水沟数。

 

题意：就是由于下大雨的时候约翰的农场就会被雨水给淹没，无奈下约翰不得不修建水沟，而且是网络水沟，并且聪明的约翰还控制了水的流速，本题就是让你求出最大流速，无疑要运用到求最大流了。题中N为水沟的顶点数，M为水沟数，接下来Si,Ei,Ci分别是水沟的起点，终点以及其容量。求源点1到终点M的最大流速。注意重边

 

附上代码：

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define INF 1e9#define xmin(a,b) a
          

q; CL(pre,0); CL(vis,false); vis[1]=true; q.push(1); while(!q.empty()) { cur=q.front(); q.pop(); if(cur==n) return true; for(int i=1; i<=n; i++) { if(!vis[i] && mat[cur][i]) { vis[i]=true; pre[i]=cur; q.push(i); } } } return false;}int max_flow(){ int ans=0; while(1) { if(!BFS()) return ans; int Min=INF; for(int i=n; i!=1; i=pre[i]) Min=xmin(Min,mat[pre[i]][i]); for(int i=n; i!=1; i=pre[i]) { mat[pre[i]][i]-=Min; mat[i][pre[i]]+=Min; } ans+=Min; }}int main(){ int i,j,T,Case; scanf("%d",&T); for(Case=1;Case<=T;Case++) { scanf("%d%d",&n,&m); CL(mat,0); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); mat[a][b]+=c; } printf("Case %d: ",Case); printf("%d\n",max_flow()); } return 0;}