HDU 3691 Nubulsa Expo (全局最小割)

我会带着你远行 2022-06-15 09:20 125阅读 0赞

题目链接：  
[点击打开题目链接][Link 1]

题意：  
给你一张图，n个点，m条无向边，每条边有权值，表示该路人流量上界。给定起点S，问如何选终点T，能是S−T的所有路径上最小人流量总和最大，让你求出这个最大流量。简而言之，就是给出一个无向图和一个源点，让你求从这个源点出发到某个点的最大流的最小值？

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

分析：如果我们用最大流去做，就需要O(n)枚举终点。再加上最大流的复杂度，至少要O(n4)，复杂度就很高了，对这题来说行不通。3004=8.1∗109。  
所以就用到Stoer−Wagner算法，最坏时间复杂度也就O(n3)。完全可行。

AC代码：

//#include <bits/stdc++.h>
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define N 500+10
    #define INF 0x3f3f3f3f
    using namespace std;
    
    int mp[N][N];
    int v[N]; // v[i]代表节点i合并到的顶点
    int dis[N];//dis数组用来表示该点与A集合中所有点之间的边的长度之和
    bool vis[N]; //是否已并入集合
    int n,m;
    int s;
    int Stoer_Wagner(int n)
    {
        int i, j, res = INF;
        for(i = 0; i < n; i ++)
            v[i] = i +1;//保存顶点 ，固定顶点为自己 
        while(n > 1)
        {
            //pre用来表示之前加入A集合的点
            //我们每次都以0点为第一个加入A集合的点 
            int k = 1, pre = 0;
            for(i = 1; i < n; i ++){
                dis[v[i]] = mp[v[0]][v[i]];
                if(dis[v[i]] > dis[v[k]])
                    k = i;
            }
            memset(vis, 0, sizeof(vis));
            vis[v[0]] = true;//标记该点已经加入A集合  
            for(i = 1; i < n; i ++)
            {
                if(i == n-1)//最后一次加入的点就要更新答案
                {
                    res = min(res, dis[v[k]]);
                    for(j = 0; j < n; j ++) //将该点合并到pre上，相应的边权就要合并  
                    {
                        mp[v[pre]][v[j]] += mp[v[j]][v[k]];
                        mp[v[j]][v[pre]] += mp[v[j]][v[k]];
                    }
                    v[k] = v[-- n];//删除最后一个点
                }
                vis[v[k]] = true;
                pre = k;
                k = -1;
                for(j = 1; j < n; j ++)
                    if(!vis[v[j]])
                    {
                        //将上次求的 k 加入集合，合并与它相邻的边到割集 
                        dis[v[j]] += mp[v[pre]][v[j]];
                        if(k == -1 || dis[v[k]] < dis[v[j]])
                            k = j;
                    }
            }
        }
        return res;
    }
    
    int main()
    {
        while(~scanf("%d%d%d", &n, &m, &s))
        {
            if(n==0&&m==0&&s==0)break;
            memset(mp, 0, sizeof(mp));
            int a, b, c;
            for(int i = 0; i < m; i++)
            {
                scanf("%d%d%d", &a, &b, &c); 
                mp[a][b] += c;
                mp[b][a] += c;
            }
            printf("%d\n", Stoer_Wagner(n));
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=3691