吐槽挖坑区

最小生成树2

字数统计: 560字   |   阅读时长: 2分
, , , ,

摘要: 最小生成树的一些衍生问题，比较难。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

  • 最小生成树方案数

题目: P4208 最小生成树计数
算法: Kruskal
题解参考: 力扣1489-找到最小生成树里的关键边和伪关键边；4208题解

  • 次小生成树

题目: 356. 次小生成树
算法: 树上倍增
题解参考: LCA,树上倍增,树上差分>

  • 最优比率生成树

题目: 348. 沙漠之王
算法：01分数规划,值域二分
题解参考: 01分数规划

  • k小生成树

题目: k小生成树(kmst)
题解参考: k小生成树题解

  • 曼哈顿距离最小生成树

题目：1584. 连接所有点的最小费用
算法：邻接矩阵 + Prim，$O(N^2)$
题解参考：

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
// O(N^2)
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<vector<int>> adj(n, vector<int>(n, 0));
        for(int i = 0; i < n - 1; ++i)
            for(int j = i + 1; j < n; ++j)
            {
                int d = manhattan(points[i][0], points[i][1], points[j][0], points[j][1]);
                adj[i][j] = adj[j][i] = d;
            }
        int cost = 0;
        vector<int> visited(n, false);
        // 选择 visited[i] && !visited[j] 的边 ij 中 adj[i][j] 最小的
        vector<int> d(n, INT_MAX / 2);
        // d[j] := !visited[j] 成立的最小的 adj[i][j]
        d[0] = 0;
        for(int cnt = 1; cnt <= n; ++cnt) // 选出 n 个点
        {
            // 选出使得 d[j] 最小的 j
            // !visited[j] 且使得 adj[i][j] 最小的 j
            int minx = INT_MAX / 2;
            int minx_j = -1;
            for(int j = 0; j < n; ++j)
            {
                if(!visited[j] && d[j] < minx)
                {
                    minx = d[j];
                    minx_j = j;
                }
            }
            cost += minx;
            visited[minx_j] = true;
            // 更新与 minx_j 关联的边
            const int &i = minx_j;
            for(int j = 0; j < n; ++j)
                if(!visited[j] && d[j] > adj[i][j])
                    d[j] = adj[i][j];
        }
        return cost;
    }

private:
    int manhattan(int x1, int y1, int x2, int y2)
    {
        return abs(x1 - x2) + abs(y1 - y2);
    }
};

算法2: 莫队算法 + 树状数组
题解参考:

Share