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

 代码：

//网络流：福特-富尔克森算法（二维数组版本）

#include<iostream>

#include<string>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=1e3+5;

int v;

int capacity[maxn][maxn],flow[maxn][maxn];

//capacity保存u到v的容量，flow保存u到v的流量，反方向时为负

//函数计算返回总流量

int networkflow(int source, int sink) {

    memset(flow,0,sizeof(flow));

    int totalflow=0;

    while(true) {

        //BFS寻找增广路径

        vector<int> parent(maxn,-1);

        queue<int> q;

        parent[source]=source;

        q.push(source);

        while(!q.empty()) {

            int here=q.front();q.pop();

            for(int there=0;there<v;++there)

                //沿着还有剩余容量的边搜索

                if(capacity[here][there]-flow[here][there]>0&&parent[there]==-1) {

                    q.push(there);

                    parent[there]=here;

                }

        }

        //没有增广路经存在

        if(parent[sink]==-1) break;

        int amount=INF;

        for(int p=sink;p!=source;p=parent[p]) {

            amount=min(capacity[parent[p]][p]-flow[parent[p]][p],amount);

        }

        //决定通过增广路径传输流

        for(int p=sink;p!=source;p=parent[p]) {

            flow[parent[p]][p]+=amount;

            flow[p][parent[p]]-=amount;

        }

        totalflow+=amount;

    }

    return totalflow;

}

int main() {

    int t,cnt=1;

    scanf("%d",&t);

    while(t--) {

        int n,m;

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

        v=n;

        memset(capacity,0,sizeof(capacity));

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

            int x,y,c;

            scanf("%d%d%d",&x,&y,&c);

            capacity[x-1][y-1]+=c;

        }

        printf("Case %d: %d\n",cnt++,networkflow(0,n-1));

    }

    return 0;

}