首页 > ACM题库 > HDU-杭电 > HDU 3549-Flow Problem-网络流-[解题报告]HOJ
2014
11-05

HDU 3549-Flow Problem-网络流-[解题报告]HOJ

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

题目:Flow Problem

 

网络流深入学习请戳这里。

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

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

径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径,沿该路径可以压入更多的流,从而增加流的值。反复进行这一过程,直至增广路

径都被找出来,根据最大流最小割定理,当不包含增广路径时,f是G中的一个最大流。

#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;
}

 

参考:http://blog.csdn.net/ACdreamers/article/details/8670111


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

  2. 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])