算法图算法

超级源

字数统计: 1.5k字   |   阅读时长: 6分
,

摘要: 超级源的处理技巧

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

超级源和超级汇是图论问题中的一个处理技巧。本文我们简要介绍一下超级源和超级汇的思想，然后解决力扣 1168。

$1 超级源和超级汇

超级源点跟超级汇点是模拟出来的虚拟点，多用在图中出现以下情况时使用：

<1> 同时有多个源点和多个汇点，建立超级源点和超级汇点

<2> 同时有多个源点和一个汇点，建立超级源点

<3> 同时有多个汇点和一个源点，建立超级汇点

一般的图论算法多是适用于一个源点到一个汇点或者是一个源点到多个汇点的类型，但是如果出现多个源点对应多个汇点时怎么办，跑多遍算法会超时。

既然是从多个源点出发到多个汇点，考虑建立一个点来代替多个源点/汇点的效果，而又不影响答案。

$2 超级源 + 最短路径

问题

给出你 n 个点，m 条有向边，每条路都有时间花费，给定一个终点，多个起点，问从起点到终点的最小时间花费是多少。

分析

如果用 Floyed 算法，时间复杂度 $O(V^{3})$ 会超时。而 Dijkstra 算法只能求单源点，这里是多源点单汇点。

可以考虑的处理方式有两种：

算法1：在反图上跑 Dijkstra，终点当起点，由于终点只有一个，满足要求。

算法2：建立一个虚拟的源点，链接所有的起点，但是路径长度为0。然后跑从超级源点到汇点的最短距离即可。

关于最短路径算法，参考文章 带权图最短路径算法与实现。

$3 超级源 + 最小生成树

题目

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。

对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井，成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）；另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j, house2j, costj] 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。

请返回 为所有房子都供水的最低总成本 。

提示：

1
2
3
4
5
6
7
8
2 <= n <= 1e4
wells.length == n
0 <= wells[i] <= 1e5
1 <= pipes.length <= 1e4
pipes[j].length == 3
1 <= house1j, house2j <= n
0 <= costj <= 1e5
house1j != house2j

示例 1：
输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
输出：3
解释：
上图展示了铺设管道连接房屋的成本。
最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。

示例 2：
输入：n = 2, wells = [1,1], pipes = [[1,2,1]]
输出：2
解释：我们可以用以下三种方法中的一种来提供低成本的水:
选项1:
在1号房子里面建一口井，成本为1
在房子2内建造井，成本为1
总成本是2。
选项2:
在1号房子里面建一口井，成本为1
-花费1连接房子2和房子1。
总成本是2。
选项3:
在房子2内建造井，成本为1
-花费1连接房子1和房子2。
总成本是2。
注意，我们可以用cost 1或cost 2连接房子1和房子2，但我们总是选择最便宜的选项。

算法：超级源 + 最小生成树

既有点权又有边权。加超级源将点权变为边权。

如果没有点权的话，直接求出最小生成树即可。

可以加超级源将点权 wells[i] 转换为边权。超级源与原图所有点 i 连边，边权为 wells[i]。因为最少有一个井，所以直接在加入了超级源的重建图上做最小生成树即可。

1
2
for(int i = 0; i < n; ++i)
    pipes.push_back(vector<int>{i + 1, n + 1, wells[i]});

关于最小生成树算法，参考文章 最小生成树。

代码 (C++)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class UnionFindSet
{
public:
    UnionFindSet(int n)
    {
        _rank = vector<int>(n, 0);
        _father = vector<int>(n, -1);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    bool same(int a, int b)
    {
        return _find(a) == _find(b);
    }

    void merge(int a, int b)
    {
        int x = _find(a);
        int y = _find(b);
        if(x == y) return;
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        return _father[x] = _find(_father[x]);
    }
};

class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        for(int i = 0; i < n; ++i)
            pipes.push_back(vector<int>{i + 1, n + 1, wells[i]});
        return mst(pipes, n + 1);
    }

private:
    int mst(vector<vector<int>>& edges, int n)
    {
        // Kruskal 接受带权边表
        sort(edges.begin(), edges.end(), Cmp());
        UnionFindSet unionfindset(n + 1);
        int cost = 0;
        int cnt = 0;
        for(const vector<int>& edge: edges)
        {
            int u = edge[0], v = edge[1], w = edge[2];
            if(unionfindset.same(u, v)) continue;
            unionfindset.merge(u, v);
            cost += w;
            ++cnt;
            if(cnt == n - 1)
                break;
        }
        if(cnt < n - 1)
            return -1;
        return cost;
    }

    struct Cmp
    {
        bool operator()(const vector<int>& edge1, const vector<int>& edge2) const
        {
            if(edge1[2] == edge2[2])
                return edge1 < edge2;
            return edge1[2] < edge2[2];
        }
    };
};
Share