oiClass-puji P2112-征兵

581 字

3 分钟

oiClass-puji P2112-征兵

2023-08-24

2023-08-30

题解

OI

/

最小生成树

原题链接

Algorithms: 最小生成树

一眼看出最小生成树#

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

依照题意，我们可以把总点数看作是 $N+M$ ，边数最多有 $R$ 条，边权为 $10000 - V_i$ ，为了给每个点一个编号，我们把女生编为 $X_i + 1$ ，男生编为 $Y_i + N + 1$ 。

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

接下来跑一遍 $Kruskal$ 就可以了。

PS: 变量解释：

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

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

5
// cnt: 统计剩余点数目

$Ac Code$

1
#include <iostream>
2
#include <algorithm>
3

4
#define endl '\n'
5

6
using namespace std;
7

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

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

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

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

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

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

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

37
inline int gid(const int &l, const bool &girl) {  // 获取节点编号
38
  if (girl) {
39
    return l + 1;
40
  } else {
41
    return l + x + 1;
42
  }
43
}
44

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

49
  cin >> t;
50
  while (t--) {
51
    cin >> x >> y >> r;
52
    n = x + y;
53
    init();
54
    for (int i = 1; i <= r; ++i) {
55
      int xi, yi, vi;
56
      cin >> xi >> yi >> vi;
57
      int xid = gid(xi, true);
58
      int yid = gid(yi, false);
59
      e[++m].u = xid;
60
      e[m].v = yid;
61
      e[m].w = ORGL - vi; // 边权为 10000 - Vi
62
    }
63

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

71
    // Kruskal 最小生成树
72
    sort(e + 1, e + m + 1);
73
    for (int i = 1; i <= m; ++i) {
74
      int fu = find(e[i].u);
75
      int fv = find(e[i].v);
76
      if (fu != fv) {
77
        fa[fu] = fv;
78
        ans += e[i].w;
79
        if (++cnt == n - 1) break;
80
      }
81
    }
82

83
    // 最终答案加上 剩余的一个点原价
84
    cout << ans + ORGL << endl;
85
  }
86
}