POJ 2912 Rochambeau

Tag: 带权并查集,枚举

题目链接 | Here

题意

author: shuri001

$n$个小伙伴进行猜拳游戏,除了一个比较聪明的家伙以外,其他人只会出单一的一种,给出$m$种猜拳的结果,要求找出那个比较聪明的小伙伴序号,并且输出在第几次猜拳可以确定?

输入

多组案例输入。

先输入$n$个人(编号从0开始),$m$种结果,然后输出一行字符串代表结果。$( 1 \leq N \leq 500 \quad 0 \leq M \leq 2000 )$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0

输出

如下所示。

1
2
3
4
Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

题解

观察发现直接判断裁判个数较为困难,并且数据规模较小(2e3*5e3),因此可以使用对枚举每个人并判断是否是裁判来求解。

假设要判断第$i$人是否为裁判,只要合并与不含此人的结果,如果没有冲突,则此人可能为裁判。

由于题目给定只能存在一个裁判因此不可能出现多裁判的情况,所以枚举出来个数为0为不可能情况,而当个数>0,则为无法分辨。

当个数为1的时候,我们显然知道这个就是裁判,但最小发现的行数如何寻找呢?起始只要仔细发现,我们在排除枚举时候,其他矛盾才能确定当前枚举的人不是裁判。

所以我们只要选择枚举中所有出现矛盾的行数的(位置)最靠后一行即可。

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
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 1e5+100;
int dsu[maxn],val[maxn];
int u[2200],v[2200];
char op[2200];

void init(int n) {for(int i=0; i<=n*3; i++) dsu[i]=i,val[i]=0;}
int find(int u) {
if(dsu[u]!=u) { int k=dsu[u]; dsu[u]=find(k); val[u]=(val[u]+val[k])%3; }
return dsu[u];
}

int merge(int a,int b,int k) {
int fa=find(a),fb=find(b);
if(fa==fb) return ((val[fa]+val[a]-val[b])%3+3)%3!=k;
dsu[fa]=fb;
val[fa]=((val[b]+k-val[a])%3+3)%3;
return 0;
}

int main() {
std::ios::sync_with_stdio(false);
int k,pos,idx,n,m,cnt;
bool flag;
while(cin >> n >> m) {
if(n==1) {
cout << "Player 0 can be determined to be the judge after 0 lines\n";
continue;
}
pos=idx=cnt=0;
for(int i=0; i<m; i++) cin >> u[i] >> op[i] >> v[i];
for(int i=0; i<n; i++) {
init(n);
flag=1;
for(int j=0; j<m; j++) {
if(u[j]==i || v[j]==i) continue;
if(op[j]=='<') k=1;
else if(op[j]=='>') k=2;
else k=0;
if(merge(u[j],v[j],k)) {
pos=max(pos,j);
flag=0;
break;
}
}
if(flag) {
cnt++;
idx=i;
}
}
if(cnt==0) cout << "Impossible\n";
else if(cnt>1) cout << "Can not determine\n";
else cout << "Player " << idx << " can be determined to be the judge after " << (pos+1) << " lines\n";
}
return 0;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ