CodeForce刷题表

Day9

1594D - The Number of Imposters

题意:

有n个人，m对关系，每对关系u , v , s 表示u说v是s。每个人有两个身份，船员和冒名者，船员的话全部为真话，冒名者的话全部为假话。问最多有多少个冒名者。

思路：

如果s是imposter那么u v一个是船员一个是冒名者，

如果s是crewmate那么u v两个都是船员或者两个都是冒名者。

用扩展域并查集来维护关系，然后遍历出坏人最多的情况。

代码:

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7; 
int f[N],siz[N];
int find(int x) {
	if(f[x] == x) return x;
	return f[x] = find(f[x]);
}
void combine(int x,int y) {
	int dx = find(x);
	int dy = find(y);
	if(dx != dy) 
		f[dx]=dy,siz[dy]+=siz[dx],siz[dx]=0; 
}
int main(){
	int _;cin>>_;
	while(_--) {
		int n,m,a,b;
		string s;
		cin>>n>>m;
		for(int i=1;i<=2*n;i++) {
			f[i] = i;
			if(i<=n)	siz[i]=0;
			else	siz[i]=1;
		}
		while(m--) {
			cin>>a>>b>>s;
			if(s=="crewmate")
				combine(a,b),combine(a+n,b+n);
			else
				combine(a,b+n),combine(a+n,b);
		}
		int res = 0;
		for(int i=1;i<=n;i++) {
			int dx = find(i);
			int dy = find(i+n);
			if(dx == dy) {
				res = -1;
				break;
			}
			if(dx==i)
				res+=max(siz[dx],siz[dy]);
		}
		cout<<res<<endl;
	} 
	return 0;
}

总结：

详细见:https://wtcsky.github.io/2021/11/11/%E3%80%8A%E5%85%B3%E4%BA%8E%E7%AE%97%E6%B3%95%E3%80%8B/%E6%89%A9%E5%B1%95%E5%9F%9F%E5%B9%B6%E6%9F%A5%E9%9B%86/