<题目链接>
题目大意：
n个人进行m轮剪刀石头布游戏(0<n<=500,0<=m<=2000)，接下来m行形如x, y, ch的输入，ch='='表示x, y平局，ch='>'表示x赢y，ch='<'表示x输y, 但是我们不知道x, y的手势是什么; 其中有一个人是裁判，它可以出任意手势，其余人手势相同的分一组，共分为三组，可以存在空组，也就是说除了裁判外，其余人每一次出的手势都相同，问能不能确定裁判是几号，如果能，输出最少在第几轮可以确定；
解题分析：
由于直接对所给的条件进行并查集处理，不容易直接找出符合要求的裁判，所以我们不妨暴力枚举裁判，因为裁判可以随便出，所以包含裁判的语句要直接跳过，不能作为判断冲突的条件，然后我们就可以遍历所有的条件，如果在当前遍历的裁判情况下，这些语句不产生冲突，说明当前遍历的裁判是可行的，裁判数量+1。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = +;
const int M = 2e3+;
int rnk[N],father[N];
int arr[M],brr[M],n,m;
char ss[M];
void init(){
for(int i=;i<n;i++){
father[i]=i;
rnk[i]=;
}
}
int find(int x){
if(father[x]==x)return x;
int tmp=father[x];
father[x]=find(father[x]);
rnk[x]=(rnk[x]+rnk[tmp]+)%;
return father[x];
}
int Union(int a,int b,int c){
int ra=find(a),rb=find(b);
if(ra==rb){ //如果根相同就直接判断是否冲突
if((rnk[a]-rnk[b]+)%!=c)return ; //冲突
return ;
}
father[ra]=rb;
rnk[ra]=(c-rnk[a]+rnk[b]+)%; //利用矢量，构造ra-->rb之间的rnk关系
return ;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=m;i++){
scanf("%d%c%d",&arr[i],&ss[i],&brr[i]);
}
int num=,loc=,ord=;
for(int i=;i<n;i++){ //暴力枚举裁判
init();
bool flag=true;
for(int j=;j<=m;j++){
if(arr[j]==i||brr[j]==i)continue; //因为裁判可以任意出，不会与其他人产生冲突，所以遇到裁判就跳过
int c;
if(ss[j]=='=')c=;
else if(ss[j]=='<')c=;
else c=;
if(Union(arr[j],brr[j],c)){ //判断是否出现矛盾
loc=max(j,loc); //(难点)维护矛盾出现的最大行数,因为如果最后只有一个裁判的话，说明其他的都不是裁判，而这里记录的每个枚举出的裁判出现矛盾的最小行数，所以，最后如果要使这些裁判全部出现矛盾的话，就记录下这些最小行数的最大值
flag=false;
break;
}
}
if(flag){
num++; //如果没有矛盾，说明这个人可以为裁判
ord=i; //记录下裁判的序号
}
}
if(!num)printf("Impossible\n");
else if(num>)printf("Can not determine\n");
else printf("Player %d can be determined to be the judge after %d lines\n", ord, loc);
}
return ;
}
2018-10-03