模板

需要读者对以下知识有所了解：权值非负最短路、权值带负数最短路、并查集

一、prim

简要介绍

和朴素版的 Dijkstra 算法 相似，区别在于 $Dijkstra$ 的 $dist$ 数组用于存储从起点到该点的最短距离；而 $prim$ 算法的 $dist$ 数组用于存储该点到集合中的任意一点的最短距离。

模板

int prim(int n)
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist); //dist数组存储点到集合的最短距离
    dist[1] = 0;//任意规定一个起点
    for(int _ = 0; _ < n; ++ _)
    {
        int t = -1;
        for(int i = 1; i <= n; ++ i)
            if(!b[i] && (t == -1 || dist[t] > dist[i]))
                t = i;

        if(dist[t] == INF) return INF; //点无法与集合连通
        b[t] = true;
        res += dist[t]; //要放在更新dist前面,不然可能产生自负环
        for(int i = 1; i <= n; ++ i)
            dist[i] = min(dist[i], a[t][i]); //与dijkstra的区别
    }
    return res;
}

二、Kruskal

简要介绍

采用了贪心策略：每次尝试将最小的边上的两点加入集合中、让这两个点连通。

模板

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

//结构体数组存储边的信息,预先按照权值从小到大排好了序
int kruskal(int n, int 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 = node[i].a, b = node[i].b, w = node[i].w;
        if(find(a) != find(b)) //a节点和b节点不在同一个集合中
        {
            res += w;
            cnt ++;
            p[find(a)] = p[find(b)]; //合并操作
        }
    }

    if(cnt != n - 1) return INF; //非连通图
    return res;
}

例题

一、求最小生成树（简单）

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

1≤n≤$10^5$,1≤m≤2∗$10^5$, 图中涉及边的边权的绝对值均不超过 1000。

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

题目分析

是算法基础课的板子题、直接套最小生成树模板即可。

参考代码1 prim

#include <bits/stdc++.h>

using namespace std;
const int N = 505, INF = 0x3f3f3f3f;
int a[N][N];
int dist[N];
bool b[N];

//详细注释写在模板里
int prim(int n)
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[n] = 0;
    for(int _ = 0; _ < n; ++ _)
    {
        int t = -1;
        for(int i = 1; i <= n; ++ i)
            if(!b[i] && (t == -1 || dist[t] > dist[i]))
                t = i;

        if(dist[t] == INF) return INF;
        b[t] = true;
        res += dist[t];
        for(int i = 1; i <= n; ++ i)
            dist[i] = min(dist[i], a[t][i]);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    memset(a, 0x3f, sizeof a);
    int n, m; cin >> n >> m;
    int x, y, z;
    for(int i = 0; i < m; ++ i)
    {
        cin >> x >> y >> z;
        a[x][y] = a[y][x] = min(a[x][y], z);
    }

    int t = prim(n);

    if(t != INF) cout << t;
    else cout << "impossible";

    return 0;
}

参考代码2 Kruskal

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5, INF = 0x3f3f3f3f;
struct Node{
    int a, b, w;
    bool operator< (const Node&W) const
    {
        return w < W.w;
    }
}node[N];
int p[N];

//详细注释写在模板里
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(int n, int 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 = node[i].a, b = node[i].b, w = node[i].w;
        if(find(a) != find(b))
        {
            res += w;
            cnt ++;
            p[find(a)] = p[find(b)];
        }
    }

    if(cnt != n - 1) return INF;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    int a, b, w;
    for(int i = 0; i < m; ++ i)
    {
        cin >> a >> b >> w;
        node[i] = {a, b, w};
    }

    sort(node, node + m);

    int t = kruskal(n, m);

    if(t == INF) cout << "impossible";
    else cout << t;

    return 0;
}

二、最短网络（简单）

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

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

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

约翰的农场的编号是1，其他农场的编号是 2∼n。为了使花费最少，他希望用于连接所有的农场的光纤总长度尽可能短。

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

输入格式

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

接下来 n 行，每行包含 n 个整数，输入一个对角线上全是0的对称矩阵。

其中第 x+1 行 y 列的整数表示连接农场 x 和农场 y 所需要的光纤长度。

输出格式

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

数据范围

3≤n≤100

每两个农场间的距离均是非负整数且不超过100000。

输入样例：

4
0  4  9  21
4  0  8  17
9  8  0  16
21 17 16  0

输出样例：

28

题目分析

很容易看出来是个最小生成树的裸题，直接套模板就AC了。

参考代码

#include <bits/stdc++.h>

using namespace std;
const int N = 105, INF = 0x3f3f3f3f;
int a[N][N];
int dist[N];
bool b[N];

//详细注释写在模板里
int prim(int n)
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int _ = 0; _ < n; ++ _)
    {
        int t = -1;
        for(int i = 1; i <= n; ++ i)
            if(!b[i] && (t == -1 || dist[t] > dist[i]))
                t = i;
        b[t] = true;
        res += dist[t];
        for(int i = 1; i <= n; ++ i)
            dist[i] = min(dist[i], a[i][t]);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for(int i = 1; i <= n; ++ i) for(int j = 1; j <= n; ++ j) cin >> a[i][j];
    int t = prim(n);
    cout << t;
    return 0;
}

三、城市通电（困难）

平面上遍布着 n 座城市，编号 1∼n。第 i 座城市的位置坐标为 ($x_i$,$y_i$)。

不同城市的位置有可能重合。

现在要通过建立发电站和搭建电线的方式给每座城市都通电。

一个城市如果建有发电站，或者通过电线直接或间接的与建有发电站的城市保持连通，则该城市通电。

在城市 i 建立发电站的花费为 $c_i$ 元。在城市 i 与城市 j 之间搭建电线所需的花费为每单位长度 $k_i$+$k_j$ 元。

电线只能沿上下左右四个方向延伸，电线之间可以相互交叉，电线都是双向的。

每根电线都是由某个城市沿最短路线搭建到另一个城市。

也就是说，如果在城市 i 与城市 j 之间搭建电线，则电线的长度为 |$x_i$−$x_j$|+|$y_i$−$y_j$|。

请问，如何合理设计通电方案，可以使得所有城市都成功通电，且花费最少？

输出最少花费和具体方案。

如果方案不唯一，则输出任意一种合理方案均可。

输入格式

第一行包含整数 n。

接下来 n 行，其中第 i 行包含两个整数 $x_i$,$y_i$，用来描述城市 i 的横纵坐标。

再一行包含 n 个整数 $c_1$,$c_2$,…,$c_n$，用来描述每个城市建立发电站的花费。

最后一行包含 n 个整数 $k_1$,$k_2$,…,$k_n$。

输出格式

第一行输出所需要的最少花费。

第二行输出一个整数 v，表示需要建立发电站的数量。

第三行输出 v 个整数，表示建立发电站的城市编号，注意输出编号要在范围 [1,n] 内。且输出编号不应重复。输出编号顺序随意。

第四行输出一个整数 e，表示需要搭建的电线数量。

接下来 e 行，每行输出两个整数 a,b，表示要在城市 a 和 b 之间搭建电线。注意，任意两个城市之间最多只需要搭建一根电线，也就是说，对于每个 (a,b)，不要有多余的 (a,b) 或 (b,a) 输出。a 和 b 不能相同，且要在范围 [1,n] 内。输出电线顺序随意。

如果答案不唯一，输出任意合理方案即可。

数据范围

对于前三个测试点，1≤n≤3。 对于全部测试点，1≤n≤2000，1≤$x_i$,$y_i$≤$10^6$，1≤$c_i$,$k_i$≤$10^9$。

输入样例1：

3
2 3
1 1
3 2
3 2 3
3 2 3

输出样例1：

8
3
1 2 3 
0

输入样例2：

3
2 1
1 2
3 3
23 2 23
3 2 3

输出样例2：

27
1
2 
2
1 2
2 3

题目分析

初始情况是所有的点建发电站，当某一个点搭电线比建站便宜时，改为搭电线。

参考代码1 prim

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
#define x first
#define y second
const int N = 2005;
int n;
bool b[N];
PII idx[N];//存城市的下标
int wc[N], wk[N]; //建厂 线
vector<int> st; //发电站
vector<PII> edge; //边与边的关系
int dist[N], distp[N];//该城市的花费 与 前驱

inline LL get_dis(int a, int b) //a b两点搭线花费
{
    return (LL)(abs(idx[a].x - idx[b].x) + abs(idx[a].y - idx[b].y)) * (wk[a] + wk[b]);
}

LL prim()
{
    LL res = 0;
    for(int i = 1; i <= n; ++ i) dist[i] = wc[i]; //每个城市单独建发电站
    for(int _ = 0; _ < n; ++ _)
    {
        int t = -1;
        for(int i = 1; i <= n; ++ i)
            if(!b[i] && (t == - 1 || dist[t] > dist[i]))
                t = i;
        b[t] = true; //下标t是当前最优解
        res += dist[t];
        if(!distp[t]) st.push_back(t); //没有前驱 该点只能建发电站
        else edge.push_back({t, distp[t]}); //有前驱 不用建站
        for(int i = 1; i <= n; ++ i)
            if(!b[i] && dist[i] > get_dis(t, i)) //搭线更经济
            {
                dist[i] = get_dis(t, i);
                distp[i] = t; //将i的前驱更新为t
            }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++ i) cin >> idx[i].x >> idx[i].y;
    for(int i = 1; i <= n; ++ i) cin >> wc[i];
    for(int i = 1; i <= n; ++ i) cin >> wk[i];

    LL t = prim(); //LL 

    cout << t << endl;
    cout << st.size() << endl;
    for(auto &i: st) cout << i << ' ';
    cout << endl << edge.size() << endl;
    for(auto &i : edge) cout << i.x << ' ' << i.y << endl;
    return 0;
}

参考代码2 Kruskal

如何表示出建厂和连电线的区别? 建厂指向一个不存在的超级源点，令建厂费为到超级源点的路径费。

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 2005;
PII idx[N];
struct Edge{
    int a, b;
    LL w;  //a指向b 权值是w
    bool operator< (const Edge& W)
    {
        return w < W.w;
    }
}edge[N * N]; //所有边与边的关系
vector<int> st;
vector<PII> se;
bool bb[N * N]; //记录某条边是否被选择
int p[N], wk[N];
int id, n;

inline LL get_dis(int idx1, int idx2) //两点之间的建边费用
{
    return (LL)(abs(idx[idx1].x - idx[idx2].x) + abs(idx[idx1].y - idx[idx2].y)) * (wk[idx1] + wk[idx2]);
}

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

LL kruskal()
{
    LL res = 0;
    for(int i = 1; i <= n; ++ i) p[i] = i;
    sort(edge, edge + id);
    for(int i = 0; i < id; ++ i)
    {
        int a = find(edge[i].a), b = find(edge[i].b);
        if(a != b)
        {
            bb[i] = true;
            res += edge[i].w;
            p[find(a)] = p[find(b)];
        }
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; ++ i)
        cin >> idx[i].x >> idx[i].y; //所有点的坐标

    int c;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> c;
        edge[id ++] = {i, 0, c}; //与超级源点连接
    }
    for(int i = 1; i <= n; ++ i) cin >> wk[i];
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j < i; ++ j)
            edge[id ++] = {i, j, get_dis(i, j)}; //电线费用

    LL t = kruskal(); 
    cout << t << endl;
    for(int i = 0; i < id; ++ i) //遍历每一条边
        if(bb[i])
            if(!edge[i].b) st.push_back(edge[i].a); //自行建厂
            else se.push_back({edge[i].a, edge[i].b}); //电线
    cout << st.size() << endl;
    for(auto &i : st) cout << i << ' ';
    cout << endl << se.size() << endl;
    for(auto &i : se) cout << i.x << ' ' << i.y << endl;
    return 0;
}

小结

• prim 要以集合的思想看待 dist 数组。
• Kruskal 用到了并查集数据结构。不在乎图的存储方式，采用贪心策略跑一遍所有的边。与之相关的有“超级源点”思想。