CSU-ACM2018暑期训练11-并查集&最小生成树 题解

文章目录
  1. 1. A - The Suspects
    1. 1.1. 题意
    2. 1.2. 思路
    3. 1.3. 代码
  2. 2. B - A Bug's Life
    1. 2.1. 题意
    2. 2.2. 思路
    3. 2.3. 代码
  3. 3. C - 食物链
    1. 3.1. 题意
    2. 3.2. 思路
    3. 3.3. 代码
  4. 4. D - X-Plosives
    1. 4.1. 题意
    2. 4.2. 思路
    3. 4.3. 代码
  5. 5. E - Almost Union-Find
    1. 5.1. 题意
    2. 5.2. 思路
    3. 5.3. 代码
  6. 6. F - True Liars
    1. 6.1. 题意
    2. 6.2. 思路
    3. 6.3. 代码
  7. 7. H - Arctic Network
    1. 7.1. 题意
    2. 7.2. 思路
    3. 7.3. 代码
  8. 8. I - There is No Alternative
    1. 8.1. 题意
    2. 8.2. 思路
    3. 8.3. 代码
  9. 9. J - Frogger
    1. 9.1. 题意
    2. 9.2. 思路
    3. 9.3. 代码

CSU-ACM2018暑期训练11-并查集&最小生成树 - Virtual Judge

A - The Suspects

题意

有n个人,m个信息,每个信息表示k个人曾经接触过。现在已知编号为0的人患有非典,问共有几个人被怀疑可能会感染。

思路

简单并查集,维护一下每个集合的大小即可。

代码

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
#include <cstdio>

const int MAXN = 3e4+10;

int n, m;
int fa[MAXN];
int cnt[MAXN];

void makeFa() {
for(int i=0; i<n; i++) {
fa[i] = i;
cnt[i] = 1;
}
}

int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx==fy) return false;
cnt[fx] += cnt[fy];
fa[fy] = fx;
return true;
}

int main() {
while(scanf("%d%d", &n, &m)==2 && (n||m)) {
makeFa();
for(int i=0; i<m; i++) {
int k, a;
scanf("%d%d", &k, &a);
for(int j=1; j<k; j++) {
int b;
scanf("%d", &b);
merge(a, b);
}
}
printf("%d\n", cnt[find(0)]);
}
return 0;
}

B - A Bug's Life

题意

教授认为有一种虫子只与性别不同虫子交互,现在给你若干组虫子交互的记录,问教授的假设是否错误。

思路

简单带权并查集。两只虫子的性别关系可以通过同一集合中的虫子的性别关系推导出。维护每只虫子与其父节点的关系即可。

代码

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
#include <cstdio>

const int MAXN = 3e4+10;

int n, m;
int fa[MAXN];
int same[MAXN];

void makeFa() {
for(int i=1; i<=n; i++) {
fa[i] = i;
same[i] = true;
}
}

int find(int x) {
if(x==fa[x]) return x;
int fx = find(fa[x]);
same[x] = same[x]==same[fa[x]];
fa[x] = fx;
return fx;
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx==fy) return same[x]!=same[y];
same[fy] = same[x]!=same[y];
fa[fy] = fx;
return true;
}

int main() {
int T;
scanf("%d", &T);
for(int cs=1; cs<=T; cs++) {
scanf("%d%d", &n, &m);
makeFa();
bool flag = true;
for(int i=0; i<m; i++) {
int a,b;
scanf("%d%d", &a, &b);
flag = flag && merge(a, b);
}
printf("Scenario #%d:\n%s bugs found!\n\n", cs, flag?"No suspicious":"Suspicious");
}
return 0;
}

C - 食物链

题意

中文题,题意也比较明确。

思路

本题的关键在于,用一种合理的方法来确定相关的鱼的关系。

显然,对于任意相关的两条鱼A、B,他们的关系只能有三种:

  • A与B是同类
  • A吃B
  • B吃A

那么我们考虑三条鱼的情况。假如我们已知A与B的关系和B与C的关系,我们能否快速得出A与C的关系呢?

这里我们使用一个技巧,将两条鱼的关系抽象为数字:

关系
A与B是同类 0
A吃B 1
B吃A 2

那么进行关系运算的方式就是:relation(a, c) = (relation(a, b) + relation(b, c)) % 3

举个例子,假如A吃B,B吃C,则relation(A, B)=1,relation(B, C)=1。经过计算,relation(A, C)=(relation(A, B)+relation(B, C))%3=2,说明C吃A,与我们的预期是相同的。

在实现的时候,我们定义一个relation数组,relation[x]表示上面所说的relation(fa[x], x),然后在find和merge的过程中维护这个relation数组就好了。

另外提一下,只有当输入的X和Y已经在同一个集合中了,这句话才有可能是假话。也就是说,当且仅当find(X)==find(Y)且relation(X, Y)!=输入的关系时,这句话是假话,其中relation(X, Y) = (relation[X]+3-relation[Y])%3。

代码

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 <cstdio>
using namespace std;

const int MAXN = 5e4+10;
int n, k;
int fa[MAXN];
int relation[MAXN];

void makeFa() {
for(int i=1; i<=n; i++) {
fa[i] = i;
relation[i] = 0;
}
}

int find(int x) {
if(x==fa[x]) return x;
int fx = find(fa[x]);
relation[x] = (relation[x]+relation[fa[x]])%3;
fa[x] = fx;
return fx;
}

bool merge(int x, int y, int r) {
int fx = find(x), fy = find(y);
if(fx==fy) return (relation[x]-relation[y]+3)%3==r;
relation[fx] = (-relation[x]+r+relation[y]+3)%3;
fa[fx] = fy;
return true;
}

int main() {
scanf("%d%d", &n, &k);
makeFa();
int ans = 0;
for(int i=0; i<k; i++) {
int d,x,y;
scanf("%d%d%d", &d, &x, &y);
if(x>n || y>n) {
ans++;
continue;
}
if(!merge(x, y, d-1))
ans++;
}
printf("%d\n", ans);
return 0;
}

D - X-Plosives

题意

有n种化合物,每种化合物由两种元素组成。当几种的化合物数量等于他们所含不同元素的数量时,就会发生爆炸。现在依次给出化合物的组成,当新的化合物与之前的化合物放在一起会发生爆炸时,就不能允许这个化合物放进来。

输出拒绝的次数。

思路

把元素看成点,化合物看成边,每次新的化合物进来当成连一条边。如果图中没有环,则每个连通分量是一棵树,其边数等于点数减1,不可能存在爆炸的情况;如果图中有环,则这个环上点数等于边数,就会爆炸。

使用并查集连边,如果要连的两个点在同一集合中,则答案加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
#include <cstdio>

const int MAXN = 1e5+10;

int fa[MAXN];

int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx==fy) return false;
fa[fx] = fy;
return true;
}

void makeFa() {
for(int i=1; i<MAXN; i++) {
fa[i] = i;
}
}

int main() {
int a,b;
while(scanf("%d", &a)==1) {
makeFa();
int ans = 0;
while(a!=-1) {
scanf("%d", &b);
if(!merge(a, b))
ans++;
scanf("%d", &a);
}
printf("%d\n", ans);
}
return 0;
}

E - Almost Union-Find

题意

初始时,一共有n个元素的组合。

给出三个操作:

  • 1 p q:合并p, q所在的集合
  • 2 p q:把p移动到q所在的集合
  • 3 p:输出p所在的集合的元素的个数和元素之和

思路

这道题除了有合并和查询操作以外,还增加了移动操作。如果直接使用元素本身作为结点下标的话,移动它会影响所有以它为根结点的子树结点。

解决方法是不使用元素本身作为结点下标(除了一开始)。每次需要移动的时候,给该元素分配一个新的结点下标,然后维护它之前所在集合的大小和元素和,再合并新的结点到目标集合中。

代码

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
#include <cstdio>

const int MAXN = 200010;
int n, m;
int fa[MAXN], cnt[MAXN], sum[MAXN], id[MAXN], idx;

int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
cnt[fy] += cnt[fx];
sum[fy] += sum[fx];
fa[fx] = fy;
}
}

void move(int item, int set) {
int fi = find(id[item]), fs = find(set);
if (fi != fs) {
cnt[fs]++;
cnt[fi]--;
sum[fs] += item;
sum[fi] -= item;
id[item] = ++idx;
fa[idx] = fs;
}
}

int main() {
while (scanf("%d%d", &n, &m) == 2) {
for (int i = 1; i <= n; i++) {
fa[i] = sum[i] = id[i] = i;
cnt[i] = 1;
}
idx = n;
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
int a, b;
scanf("%d%d", &a, &b);
merge(id[a], id[b]);
}
else if (op == 2) {
int a, b;
scanf("%d%d", &a, &b);
move(a, id[b]);
}
else {
int a;
scanf("%d", &a);
int fx = find(id[a]);
printf("%d %d\n", cnt[fx], sum[fx]);
}
}
}
return 0;
}

F - True Liars

题意

一个岛上有神与恶魔两个种族,神会说真话,恶魔会说假话。已知神与恶魔的个数,但不知道具体个人是属于哪个。

现在有n条信息,每条信息的含义是:x说y是神或不是神。

问能否确定哪些人是神。

思路

题目可以转化为,输入为“yes”说明两人是同类的,输入为“no”说明两人是不同类的。

我们最终把这一群人分成若干个大集合,每个大集合中又分为两个小集合,分别是好人和坏人,只是我们不知道哪个是好人集合,哪个是坏人集合。

因为题目已经告诉好人和坏人的个数,所以我们从这若干个大集合中每个集合挑出一个小集合,使这些小集合的大小之和等于好人数目,判断这样的情况有多少种,如果是一种,则可以确定哪些是好人哪些是坏人。

需要用到动态规划(背包)。

设数组dp[MAXP*2][MAXP],dp[i][j]代表到第i个大集合时,好人数为j的情况数。转移方程为:dp[i][j]=dp[i-1][j-a]+dp[i-1][j-b],其中a、b分别是第i个大集合中两个小集合的大小。如果dp[大集合数][好人总数]==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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXP = 310;
int n, p, q;
int fa[MAXP*2];
bool same[MAXP*2];
int dp[MAXP*2][MAXP];
int id[MAXP*2], nid;
vector<int> cnt[MAXP*2][2];

void makeFa() {
for (int i = 1; i <= p+q; i++) {
fa[i] = i;
same[i] = true;
}
}

int find(int x) {
if (x == fa[x]) return x;
int fx = find(fa[x]);
same[x] = same[x] == same[fa[x]];
fa[x] = fx;
return fx;
}

bool merge(int x, int y, bool r) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
same[fy] = same[x] == same[y] == r;
fa[fy] = fx;
return true;
}

void makeIdCnt() {
for (int i = 1; i <= p + q; i++) {
if (i == fa[i]) {
id[i] = ++nid;
}
}
for (int i = 1; i <= p + q; i++) {
int fx = find(i);
cnt[id[fx]][same[i]].push_back(i);
}
}

void solve() {
dp[0][0] = 1;
for (int i = 1; i <= nid; i++) {
for (int j = 0; j <= p; j++) {
if (cnt[i][0].size() <= j)
dp[i][j] += dp[i - 1][j - cnt[i][0].size()];
if (cnt[i][1].size() <= j)
dp[i][j] += dp[i - 1][j - cnt[i][1].size()];
}
}
if (dp[nid][p] == 1) {
vector<int> ans;
int sum = p;
for (int i = nid; i >= 1; i--) {
if (dp[i - 1][sum - cnt[i][0].size()] == 1) {
ans.insert(ans.end(), cnt[i][0].begin(), cnt[i][0].end());
sum -= cnt[i][0].size();
}
else {
ans.insert(ans.end(), cnt[i][1].begin(), cnt[i][1].end());
sum -= cnt[i][1].size();
}
}
sort(ans.begin(), ans.end());
for (int it : ans) {
printf("%d\n", it);
}
puts("end");
}
else {
puts("no");
}
}

void init() {
makeFa();
nid = 0;
memset(dp, 0, sizeof dp);
for (int i = 1; i <= p + q; i++) {
cnt[i][0].clear();
cnt[i][1].clear();
}
}

int main() {
while (scanf("%d%d%d", &n, &p, &q) == 3 && (n || p || q)) {
init();
for (int i = 0; i < n; i++) {
int a, b;
char c[4];
scanf("%d%d%s", &a, &b, c);
merge(a, b, *c == 'y');
}
makeIdCnt();
solve();
}
return 0;
}

H - Arctic Network

题意

题目的大概意思是,两个地点如果各有一个satellite channel,那么无论它们相隔多远都能通信,而如果任何一个没有satellite channel的话,就只能靠radio通信,而radio通信的成本与距离D是成正比的,现在希望让所有地点都能直接或者间接通信,问最小的D是多少。

思路

最小生成树有两个特点,一个是保证了所有边的和是最小值,另一个是保证了所有边中的最大值最小。生成树算法每选中一条边就相当于把两个点集合并成了一个点集,最后用n-1条边连成了1个点集。那么我们往回推,n-2条边就连成了2个点集,n-3条边就连成了3个点集……而就这道题而言,我们相当于去求一共有N个点集的最小生成森林,只要取够P-N条边即可。

代码

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
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>

struct Point
{
double x;
double y;
double dis(const Point& a) const {
return sqrt((x - a.x)*(x - a.x) + (y - a.y)*(y - a.y));
}
} point[500];
double lowcost[500];
bool visited[500];
int s, n;
std::multiset<double> rst;

void prim() {
memset(visited, 0, sizeof visited);
rst.clear();
for (int i = 0; i < n; i++) {
lowcost[i] = 1e308;
}
int u = 0;
for (int i = 0; i < n - 1; i++) {
visited[u] = true;
double nextlen = 1e308;
int nu = -1;
for (int v = 0; v < n; v++) {
if (!visited[v]) {
lowcost[v] = std::min(lowcost[v], point[u].dis(point[v]));
if (lowcost[v] < nextlen) {
nextlen = lowcost[v];
nu = v;
}
}
}
u = nu;
rst.insert(nextlen);
}
}

int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &s, &n);
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &point[i].x, &point[i].y);
}
prim();
std::multiset<double>::iterator it = rst.begin();
for (int i = 0; i < n - s-1; i++) {
it++;
}
printf("%.2f\n", *it);
}
return 0;
}

I - There is No Alternative

题意

给定一个N个点,M条边的简单连通无向图。 对于一个无向图来说,它的最小生成树可能不是唯一的。 问在它的所有的最小生成树中共有的边是哪几条,输出边数和权值之和。 3<=N<=500, N-1<=M<=min{50000, N(N-1)/2}

思路

首先跑一遍Kruskal,得到最小生成树的权值。 之后尝试删去图中的边,如果某一条边被删去后,最小生成树的值发生了变化(一定变大),那么说明这条边是在所有的最小生成树中都不可或缺的,那么就把这条边加入到答案中。 注意到第一次Kruskal得到的边已经包含了所有的答案,因此只要枚举这里的N-1条边即可。 边排序的复杂度被均摊了,并查集的复杂度可以忽略,因此总的复杂度是O(NM)

代码

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

const int MAXN = 510, MAXM = 50010;
int n,m;
struct Edge {
int u, v, c;
bool operator< (const Edge& b) const {
return c<b.c;
}
} e[MAXM];
int possEdge[MAXN];
int cnt;
int ans, ans1, ans2;

int fa[MAXN];

int find(int x) {
return x==fa[x]?x:fa[x]=find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx==fy)
return false;
fa[fx] = fy;
return true;
}

void makeFa() {
for(int i=1; i<=n; i++) {
fa[i] = i;
}
}

void firstKrus() {
ans = 0;
cnt = 0;
makeFa();
for(int i=0; i<m; i++) {
if(merge(e[i].u, e[i].v)) {
ans += e[i].c;
possEdge[cnt++] = i;
if(cnt==n-1)
break;
}
}
}

bool krusWithout(int ce) {
makeFa();
int sum = 0, ct = 0;
for(int i=0; i<m; i++) {
if(i==ce) continue;
if(merge(e[i].u, e[i].v)) {
ct++;
sum+=e[i].c;
if(sum>ans)
return false;
if(ct==cnt)
return true;
}
}
return false;
}

void tryCut() {
ans1 = ans2 = 0;
for(int i=0; i<cnt; i++) {
if(!krusWithout(possEdge[i])) {
ans1++;
ans2+=e[possEdge[i]].c;
}
}
}

int main() {
while(scanf("%d%d", &n, &m)==2) {
for(int i=0; i<m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
}
std::sort(e, e+m);
firstKrus();
tryCut();
printf("%d %d\n", ans1, ans2);
}
return 0;
}

J - Frogger

题意

求一条路径,从第一个点能到第二个点,并且这个路径上的最大边权是最小的。

思路

郭华阳在国家集训队论文里介绍了最小生成树的性质,就是在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
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 210;
int n;
struct Point {
int x, y;
} p[MAXN];
struct Edge {
int u, v;
double w;
bool operator< (const Edge& b) const {
return w < b.w;
}
} e[MAXN*MAXN];
int coe;
int fa[MAXN];

void makeFa() {
for (int i = 0; i < n; i++) {
fa[i] = i;
}
}

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
fa[fx] = fy;
return true;
}

int main() {
int cs = 0;
while (scanf("%d", &n) == 1 && n) {
cs++;
coe = 0;
makeFa();
for (int i = 0; i < n; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
e[coe++] = { i,j,hypot(p[i].x - p[j].x, p[i].y - p[j].y) };
}
}
sort(e, e + coe);
for (int i = 0; i < coe; i++) {
merge(e[i].u, e[i].v);
if (find(0) == find(1)) {
printf("Scenario #%d\nFrog Distance = %.3f\n\n", cs, e[i].w);
break;
}
}
}
return 0;
}
分享到 评论

评论功能暂时关闭

评论功能暂时关闭