枚举$i$,假设$i$是裁判,判断还有没有冲突(其他裁判)。
如果有,那么$i$不是裁判,同时记录判断$i$不是裁判的最早判定轮数。
如果可以确定谁是裁判,那么又怎么知道处理完几条数据之后就能确定裁判呢?
当排除完其他人都不是裁判时,裁判是谁就自然显露出来了。所以取所有出现冲突时,判定非裁判中不是裁判的轮数的最大值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=2005;
int fa[N],d[N],a[N],b[N],p[N];char c[N];
inline int get(int x)
{
if(fa[x]==x)return x;
int root=get(fa[x]);
d[x]=(d[x]+d[fa[x]])%3;
return fa[x]=root;
}
//d[x]=1 x赢了 d[x]=2 x输了
bool merge(int x,int y,int k)//x->y =k
{
int p=get(x),q=get(y);
if(p==q)
{
if(k==0&&(d[x]-d[y]+3)%3!=0)return 0;
if(k==1&&(d[x]-d[y]+3)%3!=1)return 0;
return 1;
}
fa[p]=q;
if(k==1)d[p]=(d[y]-d[x]+4)%3;
else d[p]=(d[y]-d[x]+3)%3;
return 1;
}
bool pd(int i)
{
if(c[i]=='>'&&!merge(a[i],b[i],1))return 1;
if(c[i]=='<'&&!merge(b[i],a[i],1))return 1;
if(c[i]=='='&&!merge(a[i],b[i],0))return 1;
return 0;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=m;i++)
scanf("%d%c%d",&a[i],&c[i],&b[i]),a[i]++,b[i]++;
int cnt=0,num=0;memset(p,0,sizeof(p));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)fa[j]=j,d[j]=0;
bool bk=0;
for(int j=1;j<=m;j++)
if(a[j]!=i&&b[j]!=i&&pd(j))
{
bk=1;
if(p[i]<j)p[i]=j;//假定i是裁判,但还有裁判,因此i不是裁判,记录判定i不是裁判的轮数。
break;
}
if(!bk){++cnt;num=i;}//i有可能是裁判
}
if(!cnt){puts("Impossible");}
else if(cnt==1)
{
int ans=0;
for(int i=1;i<=n;i++)
if(num!=i&&p[i]>ans)ans=p[i];
printf("Player %d can be determined to be the judge after %d lines\n", num-1, ans);
}
else puts("Can not determine");
}
return 0;
}
最后一次更新于2019-10-13
0 条评论