Flow Problem

Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 5111 Accepted Submission(s): 2385

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

Case 1: 1
Case 2: 2

Author

HyperHexagon

Source

HyperHexagon's Summer Gift (Original tasks)

Recommend

zhengfeng

题意：给你 n 个点【1 ... n】, m 条边 ( 2 <= N <= 15, 0 <= M <= 1000)

给出 m 条边的起点 x ，终点 y, 容量 c ( 1 <= C <= 1000)

求从第一个点到第 n 个点的最大容量。直接套模板即可Orz

算法：最大流增广路模板题。

注意：因为可能会出现两个点有多条边的情况,所以输入时记录容量时需要全部加起来。

最大流算法介绍：

lrj 《算法竞赛入门经典》总结：http://blog.csdn.net/cfreezhan/article/details/9366053

Accepted

3549

46MS

248K

1984 B

C++

free斩

#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;

const int maxn = 20;
const int INF = 1000000+10;

int cap[maxn][maxn]; //流量
int flow[maxn][maxn]; //容量
int a[maxn]; //a[i]：从起点 s 到 i 的最小容量
int p[maxn]; //p[i]: 记录点 i 的父亲

int main()
{
    int T;
    int n,m;
    scanf("%d", &T);
    for(int test = 1; test <= T; test++)
    {
        scanf("%d%d", &n,&m);
        memset(cap, 0, sizeof(cap)); //初始化容量为 0
        memset(flow, 0, sizeof(flow)); // 初始化流量为 0

        int x,y,c;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &x,&y,&c);
            cap[x][y] += c; // 因为可能会出现两个点有多条边的情况,所以需要全部加起来
        }
        int s = 1, t = n; // 第一个点为起点, 第 n 个点为终点

        queue<int> q;
        int f = 0; // 总流量

        for( ; ; ) // BFS找增广路
        {
            memset(a,0,sizeof(a)); //每次找增广路初始化最小残量为 0 ,所以 a[i] 同时可做标记数组
            a[s] = INF; // 起点残量无限大
            q.push(s);  // 起点入队

            while(!q.empty()) // 当队列非空
            {
                int u = q.front(); q.pop(); // 取出队首并弹出
                for(int v = 1; v <= n; v++) if(!a[v] && cap[u][v] > flow[u][v]) //找到新节点 v
                {
                    p[v] = u; q.push(v); // 记录 v 的父亲,并加入 FIFO 队列
                    a[v] = min(a[u], cap[u][v]-flow[u][v]); // s-v 路径上的最小残量【从而保证了最后,每条路都满足a[t]】
                }
            }

            if(a[t] == 0) break; // 找不到, 则当前流已经是最大流, 跳出循环

            for(int u = t; u != s; u = p[u]) // 从汇点往回走
            {
                flow[p[u]][u] += a[t]; //更新正向流
                flow[u][p[u]] -= a[t]; //更新反向流
            }
            f += a[t]; // 更新从 s 流出的总流量

        }
        printf("Case %d: %d
", test, f);

    }
    return 0;
}