在本题解前：
贴个链接，我在CSDN上的最小生成树博客：https://blog.csdn.net/qq_39561693/article/details/113576236
（只能算是学习总结吧，讲的特别透彻还不敢说）
另外别忘了专题题目链接：https://vjudge.net/contest/421050#problem/B
A - Jungle Roads
题意
题目真的好长好长……实际上就是一个裸的求最小生成树。
分析
直接Kruskal. 注意下面给出的代码是我刚刚学完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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
using namespace std;
struct edge{
char l, r;
int val;
};
bool cmp(edge a, edge b){
return a.val < b.val;
}
map<char, char> fa;
map<char, bool> vis;
map<pair<char, char>, int> w;
int n;
char find(char x){
if(fa[x] == x) return x;
return find(fa[x]);
}
int ans;
int cnt;
void unit(char x, char y){
char rx = find(x), ry = find(y);
if(rx != ry){
fa[ry] = rx;
pair<char, char> p;
p.first = x, p.second = y;
ans += w[p];
cnt++;
}
}
int main()
{
while(cin >> n && n){
ans = 0;
cnt = 0;
vis.clear();
fa.clear();
for(char a = 'A'; a <= 'Z'; ++a){
fa[a] = a;
}
vector<edge> v;
for(int i = 0; i < n - 1; ++i){
char root;
cin >> root;
int num;
cin >> num;
for(int j = 0; j < num; ++j){
char b;
int val;
cin >> b >> val;
v.push_back({root, b, val});
pair<char, char> p;
p.first = b, p.second = root;
w[p] = val;
p.first = root, p.second = b;
w[p] = val;
}
}
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < v.size(); ++i){
unit(v[i].l, v[i].r);
if(cnt == n - 1) break;
}
cout << ans << endl;
}
return 0;
}
|
B - Networking
题意&分析
仍然裸的最小生成树。这题的克鲁斯卡尔算法是自己重写了，也是之后我一直沿用的模板。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 20005;
struct edge{
int l, r, v;
}a[maxn];
int fa[maxn];
int n, m;
int find(int x){
while(fa[x] != x){
x = fa[x];
}
return x;
}
bool cmp(edge x, edge y){
return x.v < y.v;
}
int main()
{
while(cin >> n && n){
cin >> m;
for(int i = 0; i < maxn; ++i){
a[i].l = 0, a[i].r = 0, a[i].v = 0;
}
for(int i = 1; i <= m; ++i){
cin >> a[i].l >> a[i].r >> a[i].v;
}
for(int i = 1; i <= n; ++i) fa[i] = i;
sort(a + 1, a + m + 1, cmp);
int ans = 0;
int cnt = 0;
for(int i = 1; i <= m; ++i){
if(cnt == n - 1) break;
int rl = find(a[i].l);
int rr = find(a[i].r);
if(rl == rr) continue;
ans += a[i].v;
fa[rr] = rl;
cnt++;
}
cout << ans << endl;
}
return 0;
}
|
C - Building a Space Station
题意
给若干个星球，每个星球有一个球心的三维坐标和半径。各个星球之间的距离为球心的距离减去二者半径和。如果有星球之间距离小于等于半径和的，都算距离为0（这是什么设定，育碧宇宙么），构造一个连通块连通所有星球使得线路长度和最短。
分析
要自己构造边。n个星球自然有$\frac{n(n-1)}{2}$条边。这样的图应该算是稠密图了，按理说要用Prim算法更快， 不过我Kruskal也只跑了32ms就是了，上代码
代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
int n;
const int maxn = 105;
struct ball{
double x, y, z, r;
};
struct edge{
int r, l;
double val;
};
int fa[maxn * maxn];
int find(int x){
while(fa[x] != x){
x = fa[x];
}
return x;
}
bool cmp(edge a, edge b){
return a.val < b.val;
}
double cal(ball a, ball b){
double xx = a.x - b.x;
double yy = a.y - b.y;
double zz = a.z - b.z;
double ans = sqrt(xx * xx + yy * yy + zz * zz) - a.r - b.r;
return ans > 0 ? ans : 0;
}
int main(){
while(~scanf("%d", &n) && n){
ball a[n];
for(int i = 0; i < n; ++i){
scanf("%lf%lf%lf%lf", &a[i].x, &a[i].y, &a[i].z, &a[i].r);
}
vector<edge> v;
for(int i = 0; i < n; ++i){
for(int j = 0; j < i; ++j){
if(j != i)
v.push_back({i, j, cal(a[i], a[j])});
}
}
for(int i = 0; i < n; ++i) fa[i] = i;
double ans = 0;int cnt = 0;
sort(v.begin(), v.end(), cmp);
for(int i = 0; i < v.size(); ++i){
if(cnt == n - 1) break;
int ri = find(v[i].l), rj = find(v[i].r);
if(ri != rj){
cnt++;
ans += v[i].val;
fa[ri] = rj;
}
}
printf("%.3lf\n", ans);
}
return 0;
}
|
D - Constructing Roads
题意
给一个邻接矩阵表示各个节点之间的距离，求最小生成树
分析
又是稠密图，仍然硬Kruskal，438ms.有其他人100ms以下过的应该是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
62
63
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1005;
int n;
struct edge{
int l, r, val, vis;
};
bool cmp(edge x, edge y){
return x.vis == y.vis ? x.val < y.val : x.vis > y.vis;
}
int fa[maxn];
int find(int x){
while(fa[x] != x){
x = fa[x];
}
return x;
}
map<pair<int, int>, bool> mp;
int main()
{
scanf("%d", &n);
vector<edge> v;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
int x;
scanf("%d", &x);
if(i > j){
v.push_back({i, j, x, 0});
}
}
}
for(int i = 1; i <= n; ++i) fa[i] = i;
int m;
scanf("%d", &m);
for(int i = 0; i < m; ++i){
int x1, x2;
scanf("%d%d", &x1, &x2);
pair<int, int> p;
p.first = max(x1, x2), p.second = min(x1, x2);
mp[p] = 1;
}
pair<int, int> pa;
for(int i = 0; i < v.size(); ++i){
pa.first = v[i].l, pa.second = v[i].r;
if(mp[pa]) v[i].vis = 1;
}
sort(v.begin(), v.end(), cmp);
int cnt = 0, ans = 0;
for(int i = 0; i < v.size(); ++i){
int fx = find(v[i].l), fy = find(v[i].r);
if(fx == fy) continue;
cnt++;
if(!v[i].vis) ans += v[i].val;
fa[fy] = fx;
}
printf("%d", ans);
return 0;
}
|
E - Truck History
题意
此题题意理解起来稍稍有点困难。大概是给若干个字符串，字符串之间的距离为他们对应位不同的字符数量（例如aaab和babb的距离是2，第一个和第三个字符不同）。求最小生成树。
分析
最后输出的答案中$1/Q$的Q就是最小生成树的权值和。
代码
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2000 * 2000;
const int len = 7;
struct edge{
int l, r, v;
};
int fa[maxn];
int n, m;
int find(int x){
while(fa[x] != x){
x = fa[x];
}
return x;
}
bool cmp(edge x, edge y){
return x.v < y.v;
}
int check(char* a, char* b){
int ans = 0;
for(int i = 0; i < len; ++i){
if(a[i] != b[i]) ans++;
}
return ans;
}
int main()
{
while(~scanf("%d", &n) && n){
char str[n + 1][len];
for(int i = 1; i <= n; ++i){
scanf("%s", &str[i]);
}
int pos = 1;
vector<edge> v;
for(int i = 1; i < n; ++i){
for(int j = i + 1; j <= n; ++j){
v.push_back({i, j, check(str[i], str[j])});
}
}
for(int i = 1; i <= n; ++i) fa[i] = i;
sort(v.begin(), v.end(), cmp);
int ans = 0, cnt = 0;
for(int i = 0; i < v.size(); ++i){
if(cnt == n - 1) break;
int rl = find(v[i].l);
int rr = find(v[i].r);
if(rl == rr) continue;
ans += v[i].v;
fa[rr] = rl;
cnt++;
}
printf("The highest possible quality is 1/%d.\n", ans);
}
return 0;
}
|
其他
cout+iomanip不让过，printf就过了，这OJ真的是……
F - Arctic Network
题意
有很多前哨站和一些卫星，每个卫星可以保证且仅可以保证某两个前哨站顺畅通信。除此之外，两个前哨站之间没有对应卫星的必须要在距离不超过D的距离内才可以顺畅通信。
给前哨站的坐标和卫星数量p，问D的最小值。
分析
仍然是Kruskal最小生成树。贪心一下，求最小生成树的n-1条边时，利用好这p个卫星。那么其中有p条边可以免费连接。于是把最小生成树最贵的p条边去掉，剩下的边中最大的就是要求的D.
不想贴代码了……套路都差不多，读者读到这里也可以自己写吧（反正也没读者）
G - Highways
题意
经典最小生成树问题的变式。设其中有几条边已经修好了，求最小生成树。
分析
把已经修好的边的权值设为0，再Kruskal.
H - Agri-Net
题意
给邻接矩阵的裸MST.
分析
不需要分析，问就是Kruskal.不过这题我拿后来学的Prim重新算了一下，这里贴Prim的AC代码。
代码
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
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
int a[maxn][maxn];
int val[maxn * 1000];
bool v[maxn];
int n, ans;
void prim()
{
ans = 0;
memset(val, 0x3f, sizeof(val));
memset(v, 0, sizeof(v));
val[1] = 0;
for(int i = 1; i < n; ++i){
int now = 0;
for(int j = 0; j <= n; ++j){
if(!v[j] && (now == 0 || val[j] < val[now]))
now = j;
}
v[now] = 1;
for(int u = 1; u <= n; ++u){
if(!v[u]) val[u] = min(val[u], a[now][u]);
}
}
return;
}
int main()
{
while(~scanf("%d", &n))
{
memset(a, 0, sizeof(a));
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
scanf("%d", &a[i][j]);
}
}
prim();
for(int i = 2; i <= n; ++i) ans += val[i];
printf("%d\n", ans);
}
return 0;
}
|
J - The Unique MST
题意
给一个无向带权图，问它的最小生成树是否唯一，是就输出最小生成树的权值和，否就输出“Not Unique!”.
分析
首先利用Kruskal求出一个最小生成树，然后把最小生成树的一条边拿出来不用，再求最小生成树，那么在n个节点的时候就需要求n次最小生成树，比较剩下的n-1个生成树的各个权值和。不过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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 10050;
struct edge{
int l, r, w;
}a[maxn];
int fa[maxn];
int find(int x){
if(x != fa[x])
fa[x] = find(fa[x]);
return fa[x];
}
bool cmp(edge x, edge y){
return x.w < y.w;
}
int main()
{
int t;
scanf("%d", &t);
while(t--){
memset(a, 0, sizeof(a));
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 0; i < m; ++i){
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].w);
}
sort(a, a + m, cmp);
int cnt = 0, ans = 0;
vector<int> used;
for(int i = 0; i < m; ++i){
if(cnt == n - 1) break;
int rl = find(a[i].l), rr = find(a[i].r);
if(rl != rr){
cnt++;
used.push_back(i);
ans += a[i].w;
fa[rr] = rl;
}
}
bool flag = 1;
for(int i = 0; i < used.size(); ++i){
for(int x = 1; x <= n; ++x) fa[x] = x;
int cnt2 = 0, ans2 = 0;
for(int j = 0; j < m; ++j){
if(cnt2 == n - 1) break;
if(j == used[i]) continue;
int rll = find(a[j].l), rrl = find(a[j].r);
if(rll != rrl){
cnt2++;
ans2 += a[j].w;
fa[rrl] = rll;
}
}
if(cnt2 != n - 1) continue;
if(ans2 == ans){
flag = 0;
break;
}
}
if(flag)printf("%d\n", ans);
else printf("Not Unique!\n");
}
return 0;
}
|
K - 还是畅通工程
稀疏图MST裸题.
M - 畅通工程再续
题意&分析
还是带权无向图求最小生成树，不过多了限制条件。限制条件是这个距离不能小于10，也不能大于1000，否则无法连通，求的时候把这些边忽略即可。
