2014
11-05

# Flow Problem

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.

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)

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)

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Case 1: 1
Case 2: 2

Ford-Fulkerson方法依赖于三种重要思想，这三个思想就是：残留网络，增广路径和割。

Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>

const int N=1005;

int pre[N];       //保存增广路径上的点的前驱顶点
bool vis[N];
int map[N][N];    //残留网络容量

int s,t;          //s为源点，t为汇点
int n,m;

bool BFS()        //找增广路
{
int i,cur;
std::queue<int>Q;
memset(pre,0,sizeof(pre));
memset(vis,0,sizeof(vis));
vis[s]=true;    Q.push(s);
while(!Q.empty())
{
cur=Q.front();
Q.pop();

if(cur==t) return true;       //如果已达到汇点t，表明已经找到一条增广路径，返回true.
for(i=1;i<=n;i++)
{
if(!vis[i]&&map[cur][i])  //只有残留容量大于0时才存在边
{
Q.push(i);
pre[i]=cur;
vis[i]=true;
}
}
}
return false;
}

int Max_Flow()
{
int i,ans=0;
while(true)
{
if(!BFS()) return ans;     //如果找不到增广路径就返回。
int Min=999999999;
for(i=t;i!=s;i=pre[i])     //通过pre[]数组查找增广路径上的边，求出残留容量的最小值。
Min=std::min(Min,map[pre[i]][i]);
for(i=t;i!=s;i=pre[i])
{
map[pre[i]][i]-=Min;
map[i][pre[i]]+=Min;
}
ans+=Min;
}
}

int main()
{
int T,k=1;
int u,v,c;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
s=1; t=n;
memset(map,0,sizeof(map));
while(m--)
{
scanf("%d%d%d",&u,&v,&c);
map[u][v]+=c;
}
printf("Case %d: %d\n",k++,Max_Flow());
}
return 0;
}


1. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

2. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

3. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

4. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

5. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

6. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

7. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

8. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

9. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

10. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

11. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

12. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

13. 我脚得，柒公公你是F4天团里最有幽默感的。虽然你在这里的时间不长，但是已经赢得了我们的心。虽然我没有吃到茶叶蛋，但是我看了你推荐的文。虽然你每次都特别谦逊地放低身段，其实我知道你有一颗傲娇的心。柒公公，加油，什么一叨二叨的，都不如你狠狠的来一刀。

14. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

15. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）