首页 晴问-最小生成树 & 最小造路成本 & 最大删边权值 & 最小连通成本
文章
取消

晴问-最小生成树 & 最小造路成本 & 最大删边权值 & 最小连通成本

发表于 2022/08/26 更新于 2022/08/26
作者 ,
12 分钟阅读

最小生成树-Prim算法

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

#include<iostream>
#include<string>
#include<vector>
using namespace std;

struct node
{
    int v, w;
    node(int _v, int _w) :v(_v), w(_w) {}
};
const int inf = 0x3fffffff;
const int maxn = 510;
vector<vector<node>> neighbor(maxn);
int n, m, sum, dis[maxn];
bool vis[maxn] = {false};
void Prime(int s)
{

    fill(dis, dis + n, inf);
    dis[s] = 0;
    sum = 0;
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = inf;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && dis[j] < min)
            {
                min = dis[j];
                u = j;
            }
        }
        if (u == -1)
        {
            sum = -1;
            return;
        }
        vis[u] = true;
        sum += dis[u];
        for (node n : neighbor[u])
        {
            if (vis[n.v] == false && n.w < dis[n.v])
            {
                dis[n.v] = n.w;
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        neighbor[v1].emplace_back(node(v2, w));
        neighbor[v2].emplace_back(node(v1, w));
    }
    Prime(0);
    cout << sum;
}

    和Dijkstra算法很像，唯一不同的就是Dijkstra更新dis数组是更新的源点到某个点的最短距离，而Prime算法更新的是已遍历集合（即vis为true的所有节点中任意一个）到某个点的最短距离。注意：

  • 因为每次都将一个节点加入已遍历集合中，所以一定会遍历n次，如果遍历n次前就退出循环，说明不是连通图

  • 中间debug时，法线大括号括错位置了……新的错误类型，麻了

最小生成树-Kruskal算法

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int maxe = 100010;
const int maxn = 10010;
struct edge
{
    int u, v, w;
    edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {}
};
vector<edge> E;
int n, m, sum, father[maxn];
int Find(int x)
{
    int a = x;
    while (x != father[x])
    {
        x = father[x];
    }
    //路径压缩
    while (a != father[a])
    {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
bool comp(edge& e1, edge& e2)
{
    return e1.w < e2.w;
}
int Kruskal()
{
    sum = 0;
    int edgeN = 0;
    for (int i = 0; i < n; i++)
    {
        father[i] = i;
    }
    sort(E.begin(), E.end(), comp);
    for (int i = 0; i < E.size(); i++)
    {
        int u = E[i].u, v = E[i].v, w = E[i].w;
        int faU = Find(u);
        int faV = Find(v);
        if (faU != faV)
        {
            father[faV] = faU;
            sum += w;
            edgeN++;
            if (edgeN == n - 1) break;
        }

    }
    if (edgeN == n - 1) return sum;
    else return -1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        E.emplace_back(edge(u, v, w));
    }
    cout<<Kruskal();
}

    这个算法很简单，就是根据边权把边排序，判断边的两个端点是否属于一个块，不属于的话这条边就加入最小生成树中去，正所谓边贪心。注意：

  • 在find函数里，我查父亲的时候，while写成if了，麻了，这也行

  • 第二处错就是在判断是否属于一块的时候，查两个点的父亲，如果不是一个父亲，意味着不是一块，那么该边加入最小生成树的边，此时两个父亲应该选择其中一个成为对方的父亲，而不是两个点中间选一个成为对方父亲，这样的话会使答案偏小。因为本来某两个点该成为一个家族，但因为不是父亲联合了，而是父亲的孩子联合了，那么就可能导致了父亲的其他孩子没联系起来，也就是说容易误判为不是一块，那么自然也就越快结束，那么就说明边权和会变小。

最小造路成本

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 100;
const int inf = 0x3fffffff;
int w[maxn][maxn], n, dis[maxn];
bool vis[maxn] = { false };
int Prime(int s)
{
    for (int i = 0; i < n; i++)
    {
        dis[i] = inf;
    }
    dis[s] = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = inf;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && dis[j] < min)
            {
                u = j;
                min = dis[u];
            }
        }
        if (u == -1)
        {
            return -1;
        }
        sum += dis[u];
        vis[u] = true;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && w[u][j] < dis[j])
            {
                dis[j] = w[u][j];
            }
        }
    }
    return sum;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> w[i][j];
        }
    }
    cout << Prime(0);
}

    这道题使用Prime算法，因为这道题，点很少就100个，但边很多，每两个点之间就有一条边。Prime算法擅长处理点少边多的稠密图，因为邻接矩阵写法，复杂度为$O(V^2)$，使用邻接表的堆优化复杂度为$O(VlogV + E)$（我没写过这个堆优化的，所以还不知道这个E咋来的）

最大删边权值

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 100;
const int inf = 0x3fffffff;
int w[maxn][maxn], n, m, dis[maxn];
bool vis[maxn] = { false };
int Prime(int s)
{
    for (int i = 0; i < n; i++)
    {
        dis[i] = inf;
    }
    dis[s] = 0;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        int u = -1, min = inf;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && dis[j] < min)
            {
                u = j;
                min = dis[u];
            }
        }
        if (u == -1)
        {
            return -1;
        }
        sum += dis[u];
        vis[u] = true;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && w[u][j] < dis[j])
            {
                dis[j] = w[u][j];
            }
        }
    }
    return sum;
}
int main()
{
    cin >> n >> m;
    fill(w[0], w[0] + maxn * maxn, inf);
    int totalW = 0;
    for (int i = 0; i < m; i++)
    {
        int _u, _v, _w;
        cin >> _u >> _v >> _w;
        w[_u][_v] = w[_v][_u] = _w;
        totalW += _w;
    }
    int minW = Prime(0);
    if (minW == -1) cout << -1;
    else cout << totalW - minW;

}

    图方便，用了上一题的邻接矩阵，没有用物品平时经常用的邻接表，就出错了哈哈。注意：

  • 二维邻接表使用fill初始化时，要fill(w[0], w[0] + maxn * maxn, inf);这样，不加[0]就会中断
  • 在输入邻接表的时候，一定要记得邻接矩阵两个对称的位置都要赋值，就像邻接表也要往两个表里互相填值一样
  • 最后注意判定，如果Prime后返回-1了，就直接输出就行，别再减了

最小连通成本

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
85
86
87
88
89
90
91
92
93
94
95

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

struct edge
{
    int u, v, w;
    edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};
const int maxn = 100;
const int inf = 0x3fffffff;
int n, k, w[maxn][maxn], connect[maxn], father[maxn];
vector<edge> E;

bool comp(edge& e1, edge& e2)
{
    return e1.w < e2.w;
}
int Find(int x)
{
    int a = x;
    while (x != father[x])
    {
        x = father[x];
    }
    while (a != father[a])
    {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}


int Kuraskal()
{
    int sum = 0, edgeCnt = 0;
    for (int i = 0; i < n; i++)
    {
        father[i] = i;
    }
    for (int i = 0; i < k; i++)
    {
        father[connect[i]] = connect[0];
    }
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (w[i][j] != inf)
            {
                E.emplace_back(edge(i, j, w[i][j]));
            }
        }
    }
    sort(E.begin(), E.end(), comp);
    for (int i = 0; i < E.size(); i++)
    {
        int faU = Find(E[i].u);
        int faV = Find(E[i].v);
        if (faU != faV)
        {
            sum += E[i].w;
            edgeCnt++;
            father[faV] = faU;
            if (edgeCnt == n - k) return sum;
        }
    }
    return -1;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> w[i][j];
        }
    }
    for (int i = 0; i < k; i++)
    {
        cin>>connect[i];
    }
    for (int i = 0; i < k - 1; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            w[connect[i]][connect[j]] = w[connect[j]][connect[i]] = inf;
        }
    }
    cout << Kuraskal();
}

    这道题因为有的结点已经连通，那么所有连通的点之间的边都不能再选了，所以此时使用Kruskal比较方便，有两点需要注意：

  • 第一就是，因为已经有点连通了，所以就是求剩下的点和已经连通了的这一块的最小生成树，那么边等于n-k时，就算找完了

  • 第二就是，因为已经连通的结点算一个块，所以要初始化他们的父亲为同一个，不然的话，就有可能存在多条边连向这一块的不同节点，可能导致结果偏小

算法刷题
MST Prime Kruskal
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容