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

 

Sample Output

 

Author

HyperHexagon

 

Source

 

Recommend

zhengfeng   |   We have carefully selected several similar problems for you:  3572 3416 3081 3491 1533 

 

 

一个证明需要反向更新的例子：

这个图从1到6明显最的流量为3+3=6，但如果不用反向更新，由于用BFS首先找到一条路径1-2-3-6，然后1-2,2-3,3-6这几条边被更新成了0，就再也找不到增广路径到6了，而1-5-3的剩余的5个流量就无路可走了，用反向更新会再在3-2这里加一条流量为3的边，这时候1-5-3的5流量就可以通过这条边到2再到4再到6了，这就是反向更新的需要。

参考：http://blog.csdn.net/huanglianzheng/article/details/5754057

 //750MS    4216K    1444 B    C++

 #include<iostream>

 #include<queue>

 #define INF 0x7ffffff

 #define N 1005

 using namespace std;

 int g[N][N],flow[N]; //记录流量fij, 和每次的调整值flow[e]

 int father[N],vis[N]; //记录父节点 和 标记已遍历节点

 int maxflow,n,m;

 inline int Min(int a,int b)

 {

     return a<b?a:b;

 }

 void ford_fulkerson(int s,int e)

 {

     queue<int>Q;

     maxflow=;

     while(){ //调整到无增广链为止

         memset(flow,,sizeof(flow));

         memset(vis,,sizeof(vis));

         flow[s]=INF;

         Q.push(s);

         while(!Q.empty()){

             int u=Q.front();

             Q.pop();

             for(int v=;v<=n;v++){

                 if(!vis[v] && g[u][v]>){

                     vis[v]=;

                     father[v]=u;

                     Q.push(v);

                     flow[v]=Min(flow[u],g[u][v]);

                 }

             }

             if(flow[e]>){

                 while(!Q.empty()) Q.pop();

                 break;

             }

         }

         if(flow[e]==) break;

         for(int i=e;i!=s;i=father[i]){

             g[father[i]][i]-=flow[e];

             g[i][father[i]]+=flow[e];

         }

         maxflow+=flow[e];

     }

 }

 int main(void)

 {

     int t,k=;

     int a,b,c;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&n,&m);

         memset(g,,sizeof(g));

         for(int i=;i<m;i++){

             scanf("%d%d%d",&a,&b,&c);

             g[a][b]+=c;

         }

         ford_fulkerson(,n);

         printf("Case %d: %d\n",k++,maxflow);

     }

     return ;

 }