hdu3549

maksyuki 发表于 oj 分类，标签: 图论(网络流)-最大流

15 9月 2015

Flow Problem

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

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

Author

HyperHexagon

Source

HyperHexagon's Summer Gift (Original tasks)

题目类型：最大流

算法分析：直接建图使用EK算法求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

const int INF = 0x7FFFFFFF;
const int MOD = 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 66;



struct Node
{
	int c, f;//分别表示弧之间的容量和流量
};

Node edge[maxn][maxn];
//n表示顶点的个数，m表示边的个数，pre表示当前节点的前缀节点，a表示当前节点的可增广量，其中a[i] = 0表示
//当前节点不可以增广或者是还没有被访问
int n, m, pre[maxn], a[maxn];

//在调用函数前要将流量初始化成零流!!!
long long Edmonds_Karp (int s, int t)
{
    queue <int> q;
    memset (a, 0, sizeof(a));
    memset (pre, 0, sizeof(pre));
    long long maxflow = 0;

    while (1)
    {
        memset (a, 0, sizeof(a));
        a[s] = INF;//赋值INF表示源点可以满足所有邻接节点的流量需求
        q.push(s);
        while (!q.empty())
        {
            int tt = q.front(); q.pop();

            for (int i = 1; i <= n; i++)
            if(!a[i] && edge[tt][i].c > edge[tt][i].f)
            {
                pre[i] = tt;
                q.push (i);
                a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;
            }
        }

        if(a[t] == 0) break;

        for(int i = t; i != s; i = pre[i])
        {
            edge[pre[i]][i].f += a[t];
            edge[i][pre[i]].f -= a[t];
        }

        maxflow += a[t];
    }
    return maxflow;
}

int main()
{
//    ifstream cin ("aaa.txt");

//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    while (t--)
    {
        scanf ("%d%d", &n, &m);
        memset (edge, 0, sizeof (edge));
        for (int i = 1; i <= m; i++)
        {
            int u, v, w;
            scanf ("%d%d%d", &u, &v, &w);
            edge[u][v].c += w;
        }

        printf ("Case %d: %lld\n", flag++ , Edmonds_Karp (1, n));

//        cout << "Case " << flag++ << ": " << Edmonds_Karp (1, n) << endl;
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

const int INF = 0x7FFFFFFF;

const int MOD = 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 66;

struct Node

{

int c, f;//分别表示弧之间的容量和流量

};

Node edge[maxn][maxn];

//n表示顶点的个数，m表示边的个数，pre表示当前节点的前缀节点，a表示当前节点的可增广量，其中a[i] = 0表示

//当前节点不可以增广或者是还没有被访问

int n, m, pre[maxn], a[maxn];

//在调用函数前要将流量初始化成零流!!!

long long Edmonds_Karp (int s, int t)

{

queue <int> q;

memset (a, 0, sizeof(a));

memset (pre, 0, sizeof(pre));

long long maxflow = 0;

while (1)

{

memset (a, 0, sizeof(a));

a[s] = INF;//赋值INF表示源点可以满足所有邻接节点的流量需求

q.push(s);

while (!q.empty())

{

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

for (int i = 1; i <= n; i++)

if(!a[i] && edge[tt][i].c > edge[tt][i].f)

{

pre[i] = tt;

q.push (i);

a[i] = a[tt] < edge[tt][i].c - edge[tt][i].f ? a[tt]:edge[tt][i].c - edge[tt][i].f;

}

if(a[t] == 0) break;

for(int i = t; i != s; i = pre[i])

{

edge[pre[i]][i].f += a[t];

edge[i][pre[i]].f -= a[t];

}

maxflow += a[t];

}

return maxflow;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

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

memset (edge, 0, sizeof (edge));

for (int i = 1; i <= m; i++)

{

int u, v, w;

scanf ("%d%d%d", &u, &v, &w);

edge[u][v].c += w;

}

printf ("Case %d: %lld\n", flag++ , Edmonds_Karp (1, n));

// cout << "Case " << flag++ << ": " << Edmonds_Karp (1, n) << endl;

}

return 0;

}

hdu3501

hdu3579

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

hdu3549

Flow Problem

分类目录

标签云

书签

近期评论