网格

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

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

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

原题链接：AcWing 1144。

先把给的边连上，然后由于边权只有 1 和 2，那么先添加边权为 1 的边，再添加边权为 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;

const int N = 1010, M = 2*N*N;
// 并查集里面存的数据是点 因此起码要开N^2 开小了卡了我半天
int m, n, p[M], id[N][N];

struct edge {
    int a, b, w;
} e[M];
int cnt;

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

void add_edges() {
    // 纵向是 x 变化的方向, 这里的坐标和一般意义上的坐标系不同
    int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}, dw[] = {1, 2, 1, 2};
    
    for (int z = 0; z <= 1; z++)
        // n 和 m 真的很容易打错
        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];
                        if (x <= 0 || x > n || y <= 0 || y > m) continue;
                        int a = id[i][j], b = id[x][y];
                        // 按照排列枚举 必然有重复 这里只取一种情况
                        if (a < b) e[cnt++] = {a, b, dw[u]};
                    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n*m; i++) p[i] = i;
    
    // 压缩两维到一维
    for (int i = 1, t = 0; i <= n; i++)
        for (int j = 1; j <= m; j++)
            id[i][j] = t++;
    
    // 把初始化边建好
    int x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        int a = id[x1][y1], b = id[x2][y2];
        p[find(a)] = find(b);
    }
    
    add_edges();
    
    int res = 0;
    for (int i = 0; i < cnt; i++) {
        int pa = find(e[i].a), pb = find(e[i].b);
        if (pa != pb) {
            p[pa] = pb;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}

虚拟原点

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

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

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

原题链接：AcWing 1146。

可以建一个虚拟原点，它到所有结点的距离就是在这个结点上建发电站的费用，将点权转化为边权，这样就可以直接用最小生成树做了。

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
#include <iostream>
#include <algorithm>
using namespace std;

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

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        int w; cin >> w;
        e[m++] = {0, i, w};
    }
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int w; cin >> w;
            if (i < j) e[m++] = {i, j, w};
        }
    
    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);
        if (a != b) {
            p[a] = b;
            res += e[i].w;
        }
    }
    cout << res << endl;
    return 0;
}

最小生成树中第 k 大边

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

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

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

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

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

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

原题链接：AcWing 1145。

用 kruskal 算法连 n−kn-k 条边就行，例如有 5 个点，求第 2 大边，那么连 5-2=3 条边后这三条边里的最大值就是第 k 大边。

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

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

struct point {
    int x, y;
    
    double dist(point p) {
        int dx = x-p.x, dy = y-p.y;
        return sqrt(dx*dx+dy*dy);
    }
} q[N];

struct edge {
    int a, b;
    double w;
    bool operator<(const edge &e) const {
        return w < e.w;
    }
} e[M];

int p[N], n, m, k;

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

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        cin >> q[i].x >> q[i].y;
        for (int j = 1; j < i; j++) {
            e[m++] = {i, j, q[j].dist(q[i])};
        }
    }
    sort(e, e+m);
    int cnt = 0;
    double res = 0;
    for (int i = 0; i < m && cnt < n-k; i++) {
        int a = find(e[i].a), b = find(e[i].b);
        if (a != b) {
            p[a] = b;
            cnt++;
            res = e[i].w;
        }
    }
    printf("%.2lf\n", res);
    return 0;
}

最小生成树的边权和最小完全图

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

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

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

原题链接：AcWing 346。

最小生成树中的一条边连接左右两个连通块，当将它们合并成一个局部的完全图时，需要增加的边数为：

size(l)×size(r)−1\text{size}(l)\times \text{size}(r)-1

同时这些边的边权 ww 需要严格大于已经存在的边，因此 w=w0+1w=w_0+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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 7010;
int p[N], sz[N], n;
struct edge {
    int a, b, w;
    bool operator<(const edge& e) const {
        return w < e.w;
    }
} e[N];

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

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) p[i] = i, sz[i] = 1;
        
        for (int i = 0; i < n-1; i++) {
            cin >> e[i].a >> e[i].b >> e[i].w;
        }
        sort(e, e+n-1);
        int res = 0;
        for (int i = 0; i < n-1; i++) {
            int a = find(e[i].a), b = find(e[i].b);
            if (a != b) {
                p[a] = b;
                res += (sz[b]*sz[a]-1)*(e[i].w+1);
                sz[b] += sz[a];
            }
        }
        cout << res << endl;
    }
    return 0;
}

次小生成树

给 N 个点 M 条边的无向图，求严格次小生成树的边权之和，数据保证一定有解。

原题链接：AcWing 1148。

方法：

  1. 先求最小生成树，再枚举删掉某条边后求最小生成树。O(mlog⁡m+nm)O(m\log m+nm)
  2. 先求最小生成树，再枚举非树边，将该边加入树中同时去掉另一条边，使得最终仍然是一颗生成树。如果暴力预处理出最小生成树两点路径上边权最大值是 O(n2)O(n^2)，总复杂度为 O(mlog⁡m+n2+m)O(m\log m +n^2+m)

这里方法 2 中在顶点 a,ba, b 见的非树边 w0w_0 一定大于等于包含 a,ba,b 的所有树边，即 w0≥wtw_{0}\ge w_t，这可以用反证法证明：假设 ∃w0<wt\exist w_0 \lt w_t，那么删掉 wtw_t 连上 w0w_0 就构造出一个比最小生成树还小的生成树，矛盾，得证。

但是 w0=max⁡wtw_0=\max w_t 是一个可能发生的情况。设最小生成树边权之和为 SS，那么次小生成树边权之和应该为：

S′=min⁡a,b{S−wt+w0}>SS'=\min_{a,b} \{S-w_t+w_0\}>S

所以这里 wtw_t 不能只取最大值，当 w0=max⁡wtw_0 =\max w_t 时，就要让 wtw_t 取一个次大值。

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 510, M = 10010, K = 2*N;

struct edge {
    int a, b, w;
    bool f;  // 是否为树边
    bool operator<(const edge& e) const {
        return w < e.w;
    }
} edges[M];
int p[N], n, m;

// dist1: 最大值, dist2: 次大值
int h[N], w[K], e[K], ne[K], idx, dist1[N][N], dist2[N][N];

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

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

// 求从 u 出发路径上的最大值和次大值
void dfs(int u, int par, int maxd1, int maxd2, int dist1[], int dist2[]) {
    dist1[u] = maxd1;
    dist2[u] = maxd2;
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == par) continue;
        // 这个地方不要直接改 maxd1 maxd2 因为下一轮循环要用原始数据
        int t1 = maxd1, t2 = maxd2;
        if (w[i] > t1) t2 = t1, t1 = w[i];
        else if (t2 < w[i] && w[i] < t1) t2 = w[i];
        dfs(j, u, t1, t2, dist1, dist2);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i++) {
        int a, b, w; cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges+m);
    
    // 最多 500 个结点 每条边的范围是 1~1e9 所以会爆 int
    ll S = 0;
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            p[pa] = pb;
            S += w;
            edges[i].f = true;
            add(a, b, w), add(b, a, w);
        }
    }
    
    // 默认最大距离设成 -1e9 要不然不知道是真的 0 还是默认为 0
    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 (edges[i].f) continue;
        
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        // S - wt + w > S
        if (w > dist1[a][b]) {
            res = min(res, S-dist1[a][b]+w);
        } else if (w > dist2[a][b]) {
            res = min(res, S-dist2[a][b]+w);
        }
    }
    cout << res << endl;
    return 0;
}

这里 DFS 时初始最大值设为 −109-10^9 的意图是防止下面的这种情况：

对于这个图的次小生成树，应当是去掉 (2,4)(2, 4) 加上 (1,4)(1, 4) 构成的边权和为 3030 的生成树。

但如果初始化的最大值是 00，那么会使得 3→1→2→43 \to 1 \to 2 \to 4 这条路径的次大值为 00，实际上应该是 −∞-\infin，因为压根没有次大值。

当枚举到非树边 (1,4)(1, 4) 时，一切正常：

res=S−dist1(1,4)+w(1,4)=30\text{res}=S-\text{dist}_1(1, 4)+w(1, 4)=30

而当枚举到非树边 (3,4)(3, 4) 时：

dist1(3,4)=5dist2(3,4)=0res=S−dist2(3,4)+w(3,4)=20\text{dist}_1(3, 4)=5\\ \text{dist}_2(3, 4)=0\\ \text{res}=S-\text{dist}_2(3,4)+w(3,4)=20

这显然错了，因此初始化不能传 00，将 dist2(3,4)\text{dist}_2(3, 4) 设成 −109-10^9 就可以避免这个错误。