HDU3691 Nubulsa Expo（全局最小割）

Nubulsa Expo

Time Limit: 10000/3000 MS (Java/Others)
Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1444
Accepted Submission(s): 699

Problem Description

You may not hear about Nubulsa, an island country on the Pacific Ocean. Nubulsa is an undeveloped country and it is threatened by the rising of sea level. Scientists predict that Nubulsa will disappear by the year of 2012. Nubulsa government wants to host the 2011 Expo in their country so that even in the future, all the people in the world will remember that there was a country named “Nubulsa”.

As you know, the Expo garden is made up of many museums of different countries. In the Expo garden, there are a lot of bi-directional roads connecting those museums, and all museums are directly or indirectly connected with others. Each road has a tourist capacity which means the maximum number of people who can pass the road per second.

Because Nubulsa is not a rich country and the ticket checking machine is very expensive, the government decides that there must be only one entrance and one exit. The president has already chosen a museum as the entrance of the whole Expo garden, and it’s the Expo chief directory Wuzula’s job to choose a museum as the exit.

Wuzula has been to the Shanghai Expo, and he was frightened by the tremendous “people mountain people sea” there. He wants to control the number of people in his Expo garden. So Wuzula wants to find a suitable museum as the exit so that the “max tourists flow” of the Expo garden is the minimum. If the “max tourist flow” is W, it means that when the Expo garden comes to “stable status”, the number of tourists who enter the entrance per second is at most W. When the Expo garden is in “stable status”, it means that the number of people in the Expo garden remains unchanged.

Because there are only some posters in every museum, so Wuzula assume that all tourists just keep walking and even when they come to a museum, they just walk through, never stay.

Input

There are several test cases, and the input ends with a line of “0 0 0”.

For each test case:

The first line contains three integers N, M and S, representing the number of the museums, the number of roads and the No. of the museum which is chosen as the entrance (all museums are numbered from 1 to N). For example, 5 5 1 means that there are 5 museums and 5 roads connecting them, and the No. 1 museum is the entrance.

The next M lines describe the roads. Each line contains three integers X, Y and K, representing the road connects museum X with museum Y directly and its tourist capacity is K.

Please note:

1<N<=300, 0<M<=50000, 0<S,X,Y<=N, 0<K<=1000000

Output

For each test case, print a line with only an integer W, representing the “max tourist flow” of the Expo garden if Wuzula makes the right choice.

Sample Input

Sample Output

Source

2010 Asia Fuzhou Regional Contest

链接

http://acm.hdu.edu.cn/showproblem.php?pid=3691

题意

n个点m条边无向带权图，边权表示容量，给定起点S，找一个终点T，使得从S到达T的“最大流”最小。

题解

根据最大流最小割定理，此题就是求一个全局最小割。给定的源点是无用信息，因为源点一定在某个割集中，那么终点在另一个割集随便找一点即可。所以就是让你求的一个全局最小割。——传送门

全局最小割，使用stoer_wagner算法即可。如果用最大流来做，那么得枚举n个终点，时间复杂度会超，至少$O(n^4)$。

核心思想

假设s,t是图G中的两个点，把s，t合并为一个点后，得到图G/{s,t}
如果图G的最小割min-cut把s，t点分开，那么s，t的最小割也就是图G的最小割
如果图G的最小割没有把s，t点分开，那么图G/{s,t}的最小割会把s，t点分开
依据这个思想，在图G中任意选择s，t点，循环寻找最小的s-t-cut，就可以找到图G的最小割

代码

Status	Accepted
Time	608ms
Memory	2396kB
Length	1797

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 510;

int G[maxn][maxn];
int v[maxn]; // v[i]表示结点i合并到的顶点
int dis[maxn]; // dis[i]表示i与A集合张总所有点的边权之和
bool vis[maxn]; // 是否加入集合
int n, m, s;

int stoer_wagner()
{
    int tmp = inf;
    for (int i = 1; i <= n; ++i)
        v[i] = i; // 初始化点为自己
    while (n > 1)
    {
        int k = 2, pre = 1; // pre表示之前加入A集合的点
        for (int i = 2; i <= n; ++i)
        {
            dis[v[i]] = G[v[1]][v[i]]; // 每次都以1点为第一个加入A集合的点
            if (dis[v[i]] > dis[v[k]])
                k = i;
        }
        memset(vis, 0, sizeof(vis));
        vis[v[1]] = true; // 标记该点已经加入集合
        for (int i = 1; i < n; ++i)
        {
            if (i == n - 1) // 最后一次加入的点更新答案
            {
                tmp = min(tmp, dis[v[k]]);
                for (int j = 1; j <= n; ++j)  // 将该点合并到pre上，相应边权合并
                {
                    G[v[pre]][v[j]] += G[v[j]][v[k]];
                    G[v[j]][v[pre]] += G[v[j]][v[k]];
                }
                v[k] = v[n--]; // 删除最后一个点
            }
            vis[v[k]] = true;
            pre = k;
            k = -1;
            for (int j = 2; j <= n; ++j)
            {
                if (!vis[v[j]])
                {   // 将上次的k加入集合，合并与它相邻的边到割集
                    dis[v[j]] += G[v[pre]][v[j]];
                    if (k == -1 || dis[v[k]] < dis[v[j]]) // 更新k
                        k = j;
                }
            }
        }
    }
    return tmp;
}

int main()
{
    int u, v, w;
    while (scanf("%d%d%d", &n, &m, &s) != EOF)
    {
        if (n == 0 && m == 0 && s == 0)
            break;
        memset(G, 0, sizeof(G));
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            G[u][v] += w;
            G[v][u] += w;
        }
        int ans = stoer_wagner();
        printf("%d\n", ans);
    }
    return 0;
}