AcWing 练习

卡布叻_米菲 Lv2
  2023-05-13 16:35:55 2023-05-13 16:35:55 创建   2024-02-08 11:43:51 2024-02-08 11:43:51 更新      

这里主要是我刷 AcWing 题目的练习笔记

最小生成树

形成完全图

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

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

输入格式

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

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

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

输出格式

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

每个结果占一行。

数据范围

1≤N≤6000 1≤Z≤100

输入样例

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

输出样例

1
2
4
17

思路

类 Kruskal 算法

  • 个节点的树有 条边，把这 条边按照权值 从小到大排序，依次扫描每条边，执行一个类似于 Kruskal 算法的过程。

  • 设当前扫描到边 ， 所在的并查集为， 所在的并查集为 ，此时应该合并 和 。合并后的集合 构成一棵树的结构。

  • , , 若 ，则在最终的完全图中，我们肯定需要在 之间增加一条边。于是，无向边 、 中从 到 的路径、无向边 以及 中从 到 的路径共同构成一个环。如右图所示。

  • 为了保证 一定在最小生成树中，就必须让 是连接集合 与 的权值最小的边（否则就有 “用 代替 ” 的方案）。因此， 的边权应该定为 。

image-20230514103914465

  • 与 之间一共会增加 条边，所以我们把 累加到答案中。算法时间复杂度： 。
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
#include<iostream>
#include<climits>
#include<vector>
#include<cstdio>
#include<algorithm>
#include<numeric>
using namespace std;
struct edge
{
	int x, y, z;
	edge(int x, int y, int z): x(x), y(y), z(z){}
	bool operator<(edge& other)
	{
		return z<other.z;
	}
};

vector<int> father, sz;
int find(int x)
{
	if(x == father[x]) return x;
	return find(father[x]);
}

int main()
{
	int t, n;
	cin >> t;
	while(t--)
	{
		long long int ans = 0;
		cin >> n;
		
		vector<edge> graph;
		father.clear(), sz.clear(), father.resize(n+1), sz.resize(n+1);
		iota(father.begin(), father.end(), 0), sz.assign(n+1, 1);
		for(int i = 0; i<n-1; i++)
		{
			int x, y, z;
			cin >> x >> y >> z;
			graph.emplace_back(x, y, z);
		}
		
		sort(graph.begin(), graph.end());
		
		for(int i = 0; i<n-1; i++)
		{
			int x = graph[i].x, y = graph[i].y, z = graph[i].z;
			int fx = find(x), fy = find(y);
			if(fx == fy) continue;
			ans += (long long)(z+1)*(sz[fx]*sz[fy]-1);
			father[fx] = fy;
			sz[fy]+=sz[fx];
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

限度最小生成树

给定一张 N 个点M条边的无向图，求出无向图的一颗最小生成树，满足一号节点的度数不超过给定的整数 S。

分析

首先,我们要知道两个性质.

  • 一个最小生成树,它的任意一棵子树都是最小生成树.

  • 也就是一个最小生成树,实际上是由很多棵最小生成树构成的.

​ 首先，去掉号点之后，无向图可能会分成若干个连通图。可以用深度优先遍历划出图中的每个连通图。设连通图共有 个，若 ，则本ti无解。

​ 对于每个连通块，在这个连通块内部求出它的最小生成树，然后从连通块中选出一个节点 p 与 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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
using namespace std;
int n, m, s, deg, ans;
int a[32][32], d[32], conn[32];
bool v[32], c[32];
int tree[32][32];
int ver[32], p;
int f[32], fx[32], fy[32]; // (fx[i], fy[i])就是1~i路径上的最大边，边权是f[i]

void read() {
    map<string, int> h;
    cin >> m;
    h["Park"] = 1; n = 1;
    memset(a, 0x3f, sizeof(a)); // 原图对应的邻接矩阵
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        char sx[12], sy[12];
        scanf("%s%s%d", sx, sy, &z);
        if (!h[sx]) h[sx] = ++n;
        if (!h[sy]) h[sy] = ++n;
        x = h[sx], y = h[sy];
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    cin >> s;
}

void prim(int root) { // 对ver中的p个点求最小生成树
    d[root] = 0;
    for (int i = 1; i <= p; i++) {
        int x = 0;
        for (int j = 1; j <= p; j++)
            if (!v[ver[j]] && (x == 0 || d[ver[j]] < d[x])) x = ver[j];
        v[x] = true; // 进入已选集合
        for (int j = 1; j <= p; j++) {
            int y = ver[j];
            if (!v[y] && d[y] > a[x][y])
                d[y] = a[x][y], conn[y] = x;
        }
    }
    // 连通块内部的最小生成树，连边
    int closest = root;
    for (int i = 1; i <= p; i++) {
        int x = ver[i];
        if (root == x) continue;
        ans += d[x];
        tree[conn[x]][x] = tree[x][conn[x]] = d[x];
        if (a[1][x] < a[1][closest]) closest = x;
    }
    // 每个连通块跟1号点连1条边
    deg++;
    ans += a[1][closest];
    tree[1][closest] = tree[closest][1] = a[1][closest];
}

void dfs(int x) { // 找连通块
    ver[++p] = x;
    c[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] != 0x3f3f3f3f && !c[y]) dfs(y);
}

void prim_for_all_comp() {
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    memset(tree, 0x3f, sizeof(tree)); // 最小生成树对应的邻接矩阵
    c[1] = true;
    for (int i = 2; i <= n; i++)
        if (!c[i]) {
            p = 0;
            dfs(i);
            // ver中保存了连通块里面的点
            prim(i);
        }
}

void dp(int x) {
    v[x] = true;
    for (int y = 2; y <= n; y++)
        if (tree[x][y] != 0x3f3f3f3f && !v[y]) {
            if (f[x] > tree[x][y]) {
                f[y] = f[x];
                fx[y] = fx[x], fy[y] = fy[x];
            } else {
                f[y] = tree[x][y];
                fx[y] = x, fy[y] = y;
            }
            dp(y);
        }
    v[x] = false;
}

bool solve() {
    int min_val = 1 << 30, mini;
    for (int i = 2; i <= n; i++) { // 枚举从1出发的非树边(1, i)，看加哪一条
        if (tree[1][i] != 0x3f3f3f3f || a[1][i] == 0x3f3f3f3f) continue;
        // 加入非树边(1, i)，删去树边(fx[i], fy[i])
        if (a[1][i] - tree[fx[i]][fy[i]] < min_val) {
            min_val = a[1][i] - tree[fx[i]][fy[i]];
            mini = i;
        }
    }
    if (min_val >= 0) return false;
    ans += min_val;
    tree[1][mini] = tree[mini][1] = a[1][mini];
    tree[fx[mini]][fy[mini]] = tree[fy[mini]][fx[mini]] = 0x3f3f3f3f;
    // 重新计算以mini为根的子树的dp状态
    f[mini] = a[1][mini];
    fx[mini] = 1, fy[mini] = mini;
    v[1] = true;
    dp(mini);
    return true;
}

int main() {
    read();
    // 删掉1号点，找出每个连通块，各自求Prim
    prim_for_all_comp();
    memset(v, 0, sizeof(v));
    dp(1);
    while (deg < s) {
        if (!solve()) break;
        deg++;
    }
    printf("Total miles driven: ");
    cout << ans << endl;
}
  • 标题: AcWing 练习
  • 作者: 卡布叻_米菲
  • 创建于 : 2023-05-13 16:35:55
  • 更新于 : 2024-02-08 11:43:51
  • 链接: https://carolinebaby.github.io/2023/05/13/AcWing/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
AcWing 练习
  1. 最小生成树
    1. 形成完全图
    2. 限度最小生成树