【图论】最小生成树

（算法基础+提高课笔记

基本方法

Kruskal算法

步骤与基本思路

（1）初始化所有点，每个点单独在一个点集。把所有边按权重排序

（2）按边权重从小到大遍历每一条边，如果这条边的两个顶点不在同一个点集，就将它们加到同一点集，也就是选中这条边，以此类推

（3）如果最后加入同一个点集的点个数小于n个说明这个图不是连通图，无法生成最小生成树

Kruskal板子

struct Edge
{
    int a, b, w;
    bool operator< (const Edge &W) const
    {
        return w < W.w;
    }
}edges[M];

int find(int x) // 判断x属于哪一个点集
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m); // 所有边按权重排序

    for (int i = 1; i <= n; i ++ ) p[i] = i; // 所有点单独占一个点集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) // 从小到大遍历每条边
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b) // 判断ab在不在同一个点集
        {
            p[a] = b; // 合并到同一点集
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF; // 不是连通图
    return res;
}
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

Prim算法

步骤与基本思路

（1）初始化距离数组dist[N]，将其所有值赋为0x3f

（2）从第一个点开始循环n次（因为最小生成树有n个点），每次循环中遍历所有点，选择还没有加入最小生成树且与生成树集合距离最短的点加入生成树，然后更新所有点到生成树集合的距离

（3）如果不是第一个点且距离生成树集合为无穷大时，说明不能形成最小生成树

Prim板子

int prim() // 返回最小生成树的权重和
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) // 找到距离生成树集合距离最短的点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF; // 距离最短的点距离时INF

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]); // 更新所有点到生成树集合的距离
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

​

理论基础

最小生成树

求最小生成树的基本算法有两个：

• Prim 时间复杂度O(n²)
• Kruskal 时间复杂度O(mlogn) 一般都用这个

上两个算法的证明思路：

假设不选当前边，最终得到了一棵树，然后将这条边加上，必然会出现一个环，在环上一定可以找到一条长度不小于当前边的边，那么用当前边替换，结果一定不会变差

同时还需要掌握：

• 任意一棵最小生成树一定 可以 包含无向图中权值最小的边
• 给定一张无向图G = (V, E)，n = |V|，m = |E|，从 E 中选出 k < n - 1 条边构成 G 的一个生成森林，若再从剩余的 m - k 条边中选 n - 1 - k 条边添加到生成森林中，使其成为 G 的生成树，并且选出的边的权值之和最小，则该生成树一定 可以 包含 m - k 条边中连接生成森林的两个不连通节点的权值最小的边

（证明思路还是同上）

次小生成树

定义：给定一个带权图，把图的所有生成树权值从大到小排序，第二小的称为次小生成树

严格的次小生成树权值和不能等于最小生成树

求法：

方法一：先求最小生成树，再枚举删去最小生成树中的边求解
只能求出非严格最小生成树
时间复杂度：O(mlogn + mn)

方法二：先求最小生成树，然后依次枚举非树边，将该边加入树中，同时从形成的环的其余边中去掉最大边，使得最终图依然是一棵树，一定可以求出次小生成树
时间复杂度：O(m + n² + mlogn)

基础应用

最短网络

原题链接

农夫约翰被选为他们镇的镇长！

他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。

约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。

约翰的农场的编号是1，其他农场的编号是 2∼n。

为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。

你将得到一份各农场之间连接距离的列表，你必须找出能连接所有农场并使所用光纤最短的方案。

输入格式

第一行包含一个整数 n，表示农场个数。

接下来 n 行，每行包含 n 个整数，输入一个对角线上全是0的对称矩阵。
其中第 x+1 行 y 列的整数表示连接农场 x 和农场 y 所需要的光纤长度。

输出格式

输出一个整数，表示所需的最小光纤长度。

数据范围

$3\le n\le 100$
每两个农场间的距离均是非负整数且不超过100000。

输入样例

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0
1
2
3
4
5

输出样例

28
1

题意

最小生成树裸题

思路

跑一遍prim

代码

#include 

using namespace std;

const int N = 110;

int n;
int w[N][N]; // 邻接矩阵
int dist[N]; // dist[i]表示i点距离当前连通块最短的一条边的长度
bool st[N];

int prim()
{
    int res = 0;
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i ++ ) // 需要加入n个点
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 找到距离当前连通块最短的一条边
        
        res += dist[t]; // 把最短的边连接的点加到连通块中
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]); // 更新dist
    }

    return res;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    cout << prim() << '\n';
}
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

局域网

原题链接

某个局域网内有 n 台计算机和 k 条 双向 网线，计算机的编号是 1∼n。由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。

注意：
对于某一个连接，虽然它是双向的，但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
两台计算机之间最多只会存在一条连接。
不存在一条连接，它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 f(i,j) 表示 i,j 之间连接的畅通程度，f(i,j) 值越小表示 i,j 之间连接越通畅。

现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），并且被除去网线的 Σf(i,j) 最大，请求出这个最大值。

输入格式

第一行两个正整数 n,k。

接下来的 k 行每行三个正整数 i,j,m 表示 i,j 两台计算机之间有网线联通，通畅程度为 m。

输出格式

一个正整数，表示被除去网线的 Σf(i,j) 的最大值。

数据范围

$1\le n\le 100$
$0\le k\le 200$
$1\le f(i,j)\le 1000$

输入样例

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
1
2
3
4
5
6

输出样例

8
1

题意

f[i][j]表示ij间网络通畅度，越大流畅度越差，现在给出一张图，删掉任意条边使得原来连通的点对还连通，问删去后的图的最小权重

思路

题意可转换成寻找一个“森林”的“最小生成森林”，跑一遍Kruskal即可

代码

#include 

using namespace std;

const int N = 110, M = 210;

int n, m;
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &t)const
    {
        return w < t.w;
    }
}e[M];
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }

    sort(e, e + m);

    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b) p[a] = b;
        else res += w;
    }

    cout << res << '\n';
}
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

繁忙的都市

原题链接

城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。

城市C的道路是这样分布的：

城市中有 n 个交叉路口，编号是 1∼n，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。

这些道路是 双向 的，且把所有的交叉路口直接或间接的连接起来了。

每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。

但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2．在满足要求1的情况下，改造的道路尽量少。

3．在满足要求1、2的情况下，改造的那些道路中分值最大值尽量小。

作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。

输入格式

第一行有两个整数 n,m 表示城市有 n 个交叉路口，m 条道路。

接下来 m 行是对每条道路的描述，每行包含三个整数u,v,c 表示交叉路口 u 和 v 之间有道路相连，分值为 c。

输出格式

两个整数 s,max，表示你选出了几条道路，分值最大的那条道路的分值是多少。

数据范围

$1\le n\le 300,$
$1\le m\le 8000,$
$1\le c\le 10000$

输入样例

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
1
2
3
4
5
6

输出样例

3 6
1

题意

给出一张图，问最小生成树的最大边

思路

跑一遍Kruskal即可

代码

#include 

using namespace std;

const int N = 310, M = 10010;

int n, m;
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}e[M];
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        e[i] = {a, b, c};
    }

    sort(e, e + m);

    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res = w;
        }
    }

    cout << n - 1 << ' ' << res << '\n';
}
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

连接格点

原题链接

有一个 m 行 n 列的点阵，相邻两点可以相连。

一条纵向的连线花费一个单位，一条横向的连线花费两个单位。

某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。

输入格式

第一行输入两个正整数 m 和 n。

以下若干行每行四个正整数 x1,y1,x2,y2，表示第 x1 行第 y1 列的点和第 x2 行第 y2 列的点已经有连线。

输入保证|x1−x2|+|y1−y2|=1。

输出格式

输出使得连通所有点还需要的最小花费。

数据范围

$1\le m,n\le 1000$
$0\le 已经存在的连线数\le 10000$

输入样例

2 2
1 1 2 1
1
2

输出样例

3
1

题意

给出一个点阵，相邻两点可连接，竖着连权重1，横着连权重二，已经连了一些边，求最小生成树

思路

首先还是将已经连的边存进去，然后由于竖着的比横着的权重小，我们先将竖着的边存进去再存横着的边（避免对边的集合进行排序），之后跑一遍kruskal即可

代码

#include 

using namespace std;

const int N = 1010, M = N * N, K = 2 * N * N;

int n, m, k;
int ids[N][N];
struct Edge
{
    int a, b, w;
}e[K];

int p[M];

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void get_edges()
{
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, dw[4] = {1, 2, 1, 2};

    for (int z = 0; z < 2; z ++ ) // 先竖再横 确保边权有序 使无需对边排序
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                for (int u = 0; u < 4; u ++ )
                    if (u % 2 == z)
                    {
                        int x = i + dx[u], y = j + dy[u], w = dw[u];
                        if (x && x <= n && y && y <= m) // 确定位置合法
                        {
                            int a = ids[i][j], b = ids[x][y];
                            if (a < b) e[k ++ ] = {a, b, w};
                        }
                    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++, t ++ )
            ids[i][j] = t;

    for (int i = 1; i <= n * m; i ++ ) p[i] = i;

    int x1, x2, y1, y2;
    while (cin >> x1 >> y1 >> x2 >> y2)
    {
        int a = ids[x1][y1], b = ids[x2][y2];
        p[find(a)] = find(b);
    }

    get_edges();

    // 跑一遍Kruskal
    int res = 0;
    for (int i = 0; i < k; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }

    cout << res << '\n';
}
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

拓展应用

新的开始

原题链接

发展采矿业当然首先得有矿井，小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n 口矿井，但他似乎忘记了考虑矿井供电问题。

为了保证电力的供应，小 FF 想到了两种办法：

在矿井 i 上建立一个发电站，费用为 vi（发电站的输出功率可以供给任意多个矿井）。将这口矿井 i 与另外的已经有电力供应的矿井 j 之间建立电网，费用为 pi,j。

小 FF 希望你帮他想出一个保证所有矿井电力供应的最小花费方案。

输入格式

第一行包含一个整数 n，表示矿井总数。

接下来 n 行，每行一个整数，第 i 个数 vi 表示在第 i 口矿井上建立发电站的费用。

接下来为一个 n×n 的矩阵 P，其中 pi,j 表示在第 i 口矿井和第 j 口矿井之间建立电网的费用。

数据保证 p[i,j]=p[j,i]，且 p[i,i]=0。

输出格式

输出一个整数，表示让所有矿井获得充足电能的最小花费。

数据范围

$1\le n\le 300,$
$0\le vi,pi,j\le 105$

输入样例

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
1
2
3
4
5
6
7
8
9

输出样例

9
1

题意

多个矿井需要通电，可以在矿井处建发电站也可以将该矿井和其他有点的地方连起来，这两个操作都需要一定花费，求最少花费

思路

虚拟源点

建立虚拟源点，在某点建立发电站转化成在该点和虚拟源点之间连边，边的权值是在该点建立发电站的花费，求最小生成树跑一遍Prim即可

代码

#include 

using namespace std;

const int N = 310;

int n;
int w[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, 0x3f3f3f3f, sizeof dist);
    dist[0] = 0;

    int res = 0;
    for (int i = 0; i < n + 1; i ++ )
    {
        int t = -1;
        for (int j = 0; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        
        st[t] = true;
        res += dist[t];

        for (int j = 0; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i ++ ) // 连接虚拟源点和各个点
    {
        cin >> w[0][i];
        w[i][0] = w[0][i];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    cout << prim() << '\n';
}
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

北极通讯网络

原题链接

北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。

为了加强联系，决定在村庄之间建立通讯网络，使每两座村庄之间都可以直接或间接通讯。

通讯工具可以是无线电收发机，也可以是卫星设备。

无线电收发机有多种不同型号，不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d，就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。现在要先选择某一种型号的无线电收发机，然后统一给所有村庄配备，数量不限，但型号都是 相同的。

配备卫星设备的两座村庄无论相距多远都可以直接通讯，但卫星设备是 有限的，只能给一部分村庄配备。

现在有 k 台卫星设备，请你编一个程序，计算出应该如何分配这 k 台卫星设备，才能使所配备的无线电收发机的 d 值最小。

例如，对于下面三座村庄：

其中，|AB|=10,|BC|=20,|AC|=105√≈22.36。

如果没有任何卫星设备或只有 1 台卫星设备 (k=0 或 k=1)，则满足条件的最小的 d=20，因为 A 和 B，B 和 C 可以用无线电直接通讯；而 A 和 C 可以用 B 中转实现间接通讯 (即消息从 A 传到 B，再从 B 传到 C)；

如果有 2 台卫星设备 (k=2)，则可以把这两台设备分别分配给 B 和 C ，这样最小的 d 可取10，因为 A 和 B 之间可以用无线电直接通讯；B 和 C 之间可以用卫星直接通讯；A 和 C
可以用 B 中转实现间接通讯。

如果有 3 台卫星设备，则 A,B,C 两两之间都可以直接用卫星通讯，最小的 d 可取 0。

输入格式

第一行为由空格隔开的两个整数 n,k;

接下来 n 行，每行两个整数，第 i 行的 xi,yi 表示第 i 座村庄的坐标 (xi,yi)。

输出格式

一个实数，表示最小的 d 值，结果保留 2 位小数。

数据范围

$1\le n\le 500,$
$0\le x,y\le 104,$
$0\le k\le 100$

输入样例

3 2
10 10
10 0
30 0
1
2
3
4

输出样例

10.00
1

题意

有无线电和卫星设备两种方式，无线电的参数d表示在d之内的都可以直接传输，卫星设备不管离多远都可以传输，现有k个卫星设备，求问最小的d

思路

Kruskal的基本思路是，假设已经遍历完前i条边，那么就已经求出了连接前i条边的连通块个数，本题给出k个卫星设备，意思就是我们需要求出一个d，使得距离比d小的两个点之间都靠无线电传输（这些靠无线电传输的构成了多个连通块），在所有连通块之间建立卫星设备，卫星设备的个数是k

代码

#include 

using namespace std;

typedef pair<int, int> PII;

const int N = 510, M = N * N / 2;

int n, k, m;
struct Edge
{
    int a, b;
    double w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}e[M];
PII q[M];
int p[N];

double get_dist(PII a, PII b)
{
    int dx = a.first - b.first;
    int dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) cin >> q[i].first >> q[i].second;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < i; j ++ )
            e[m ++ ] = {i, j, get_dist(q[i], q[j])};

    sort(e, e + m);
    for (int i = 0; i < n; i ++ ) p[i] = i;

    int cnt = n;
    double res = 0;

    for (int i = 0; i < m; i ++ )
    {
        if (cnt == k) break;

        int a = find(e[i].a), b = find(e[i].b);
        double w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            cnt -- ;
            res = w;
        }
    }

    printf("%.2lf\n", res);
}
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

走廊泼水节

原题链接

给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

输入格式

第一行包含整数 t，表示共有 t 组测试数据。

对于每组测试数据，第一行包含整数 N。

接下来 N−1 行，每行三个整数 X,Y,Z，表示 X 节点与 Y 节点之间存在一条边，长度为 Z。

输出格式

每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

数据范围

$1\le N\le 6000$
$1\le Z\le 100$

输入样例

2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5
1
2
3
4
5
6
7
8

输出样例

4
17
1
2

题意

将一棵树扩展为一个完全图，要求图的最小生成树还是原来的那棵树，求添加的边权总和最小是多少

思路

扩展应用

将图中每个点看做一个连通块

每两个连通块之间构成完全图就是连接两个连通块的所有点对，也就是(sized[a] * sized[b] - 1)

因为我们要让起初的树是完全图的最小生成树，我们将边权从小到大排序，每次选择当前边所连接的两个连通块，加上的新边必须要大于当前边权（才能使其为最小生成树），也就是新加的边权是w + 1

记得维护size和p

代码

#include 

using namespace std;

const int N = 6010;

int n;
struct Edge
{
    int a, b, w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}e[N];
int p[N]; // 并查集
int sized[N]; // 只有根结点的数据正确 表示这个连通块的结点个数

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n - 1; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            e[i] = {a, b, c};
        }

        sort(e, e + n - 1);
        for (int i = 1; i <= n; i ++ ) p[i] = i, sized[i] = 1;

        int res = 0;
        for (int i = 0; i < n - 1; i ++ )
        {
            int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
            if (a != b)
            {
                res += (sized[a] * sized[b] - 1) * (w + 1);
                sized[b] += sized[a];
                p[a] = b;
            }
        }

        cout << res << '\n';
    }
}
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

秘密的牛奶运输

原题链接

农夫约翰要把他的牛奶运输到各个销售点。

运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。

运输的总距离越小，运输的成本也就越低。

低成本的运输是农夫约翰所希望的。

不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。

现在请你帮忙找到该运输方案。

注意：

如果两个方案至少有一条边不同，则我们认为是不同方案；
费用第二小的方案在数值上一定要严格大于费用最小的方案；
答案保证一定有解；

输入格式

第一行是两个整数 N,M，表示销售点数和交通线路数；

接下来 M 行每行 3 个整数 x,y,z，表示销售点 x 和销售点 y 之间存在线路，长度为 z。

输出格式

输出费用第二小的运输方案的运输总距离。

数据范围

$1\le N\le 500,$
$1\le M\le 104,$
$1\le z\le 109,$
数据中可能包含重边。

输入样例

4 4
1 2 100
2 4 200
2 3 250
3 4 100
1
2
3
4
5

输出样例

450
1

题意

次小生成树板题

思路

次小生成树

使用方法二，具体步骤：

1. 求最小生成树，统计每条边是树边还是非树边，同时建立最小生成树
2. 预处理任意两点间边权最大值dist1[a][b]和次大值dist2[a][b]
3. 依次枚举所有非树边，求min(sum + w - dist[a][b])，满足w > dist1[a][b]或w > dist2[a][b]（这样才能保证求出的是严格次小生成树）

代码

#include 

using namespace std;

typedef long long ll;

const int N = 510, M = 10010;

int n, m;
struct Edge
{
    int a, b, w;
    bool f; // 记录该边是否为树边
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}edge[M];
int p[N];
int dist1[N][N], dist2[N][N];
int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// u当前结点 fa父结点 maxd1 maxd2 d1:和u形成的路径上的最大边 d2:和u形成的路径上的次大边
void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
    d1[u] = maxd1, d2[u] = maxd2; // 记录最大边次大边
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != fa) // 不是连到父结点的边再继续
        {
            // 更新当前最大边和次大边
            int td1 = maxd1, td2 = maxd2;
            if (w[i] > td1) td2 = td1, td1 = w[i];
            else if (w[i] < td1 && w[i] > td2) td2 = w[i];
            dfs(j, u, td1, td2, d1, d2);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }

    sort(edge, edge + m);
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    ll sum = 0;
    // 先跑一遍最小生成树
    for (int i = 0; i < m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb)
        {
            p[pa] = pb;
            sum += w;
            add(a, b, w), add(b, a, w);
            edge[i].f = true;
        }
    }

    // 预处理两点之间路径上的最大边和次大边
    for (int i = 1; i <= n; i ++ ) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);

    ll res = 1e18;
    for (int i = 0; i < m; i ++ )
        if (!edge[i].f) // 非树边
        {
            int a = edge[i].a, b = edge[i].b, w = edge[i].w;
            ll t;
            if (w > dist1[a][b]) t = sum + w - dist1[a][b]; // 大于当前最大边直接替换最大边
            else if (w > dist2[a][b]) t = sum + w - dist2[a][b]; // 不大于最大边但大于次大边替换次大边
            res = min(res, t);
        }

    cout << res << '\n';
}
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
96
97
98
99