oiClass-puji P2112-征兵

Horean0574 rp++

原题链接

Algorithms: 最小生成树


一眼看出最小生成树

赛时不小心把存边数组开大了,结果 MLE……

依照题意,我们可以把总点数看作是 ,边数最多有 条,边权为 ,为了给每个点一个编号,我们把女生编为 ,男生编为

因为可能不止一个需要单独征集的士兵,所以我们需要建立一个 0号 虚拟点,与全部其他节点相连,权值为 ,但这个时候边数最多就有 条了(注意数组大小)。

接下来跑一遍 就可以了。

PS: 变量解释:

1
2
3
4
5
// t: T, x: N, y: M, r: R

// n: 总点数, m: 总边数

// cnt: 统计剩余点数目

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
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;

struct Edge { // 存边结构体
int u, v, w;

bool operator < (const Edge &A) const { // 重载排序运算符
return w < A.w;
}
};

const int N = 2e4 + 5;
const int M = 9e4 + 5;
const int ORGL = 1e4; // 征集士兵原价 10000

int t, x, y, r;
int n, m, cnt, ans;
int fa[N]; // 并查集 fa 数组
struct Edge e[M]; // 存边数组

inline void init() { // 多组数据,记得重置
ans = cnt = m = 0;

for (int i = 1; i <= n; ++i) { // 并查集初始化
fa[i] = i;
}
}

inline int find(const int &l) { // 并查集 find
return fa[l] == l ? l : fa[l] = find(fa[l]);
}

inline int gid(const int &l, const bool &girl) { // 获取节点编号
if (girl) {
return l + 1;
} else {
return l + x + 1;
}
}

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

cin >> t;
while (t--) {
cin >> x >> y >> r;
n = x + y;
init();
for (int i = 1; i <= r; ++i) {
int xi, yi, vi;
cin >> xi >> yi >> vi;
int xid = gid(xi, true);
int yid = gid(yi, false);
e[++m].u = xid;
e[m].v = yid;
e[m].w = ORGL - vi; // 边权为 10000 - Vi
}

// 虚拟 0 号节点
for (int i = 1; i <= n; ++i) {
e[++m].u = 0;
e[m].v = i;
e[m].w = ORGL;
}

// Kruskal 最小生成树
sort(e + 1, e + m + 1);
for (int i = 1; i <= m; ++i) {
int fu = find(e[i].u);
int fv = find(e[i].v);
if (fu != fv) {
fa[fu] = fv;
ans += e[i].w;
if (++cnt == n - 1) break;
}
}

// 最终答案加上 剩余的一个点原价
cout << ans + ORGL << endl;
}
}
  • Title: oiClass-puji P2112-征兵
  • Author: Horean0574
  • Created at : 2023-08-24 12:08:30
  • Updated at : 2023-08-30 22:45:26
  • Link: https://blog.hxrch.top/2023/08/24/oiClass-puji-P21120-征兵/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
oiClass-puji P2112-征兵