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.
InputThe 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)OutputFor 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<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int const inf = 0x3f3f3f3f;
int c[1005][1005];//容量
int f[1005][1005];//当前流量
int minn[1005];//每次bfs中的流过每个节点的最小残留量。
int p[1005];//先驱节点~~在每次bfs后更新f数组；
int m, n;
int bfs(int s,int t)
{
	queue<int>q;
	int fl = 0;
	memset(f, 0, sizeof(f));
	while (1)
	{
		memset(minn, 0, sizeof(minn));
		minn[s] = inf;
		q.push(s);
		while (!q.empty())
		{
			int u = q.front();
			q.pop();
			for (int v = 1; v <= m; v++)
			{
				if (!minn[v] && c[u][v] > f[u][v])
				{
					p[v] = u;
					q.push(v);
					minn[v] = min(minn[u], c[u][v] - f[u][v]);
				}
			}
		}
		if (!minn[t])
		{
			break;
		}
		for (int u = t; u != s; u = p[u])
		{
			f[p[u]][u] += minn[t];//流量的增加
			f[u][p[u]] -= minn[t];//建立反向道路
		}
		fl += minn[t];
	}
	return fl;
}
int main()
{
	int t;
	cin >> t;
	int te = 1;
	while (t--)
	{
		scanf("%d%d", &m, &n);
		memset(c, 0, sizeof(c));
		memset(p, 0, sizeof(p));
		for (int s = 1; s <= n; s++)
		{
			int u, v, w ;
			scanf("%d%d%d", &u, &v, &w);
			c[u][v] += w;
		}
		printf("Case %d: %d\n",te++, bfs(1, m));
	}
	return 0;
}