这题是POJ1182食物链的升级版,先做那题,这题应该也没问题了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int NN=550; const int MM=2100; int n,m; struct Rec{ int a,b,c; Rec() {} Rec(int _a,int _b,int _c): a(_a),b(_b),c(_c) {} }e[MM]; int p[NN],r[NN]; int find(int x) { if (p[x]!=x) { int t=p[x]; p[x]=find(p[x]); r[x]=(r[x]+r[t])%3; } return p[x]; } inline void Union(int c,int a,int b) { int x=find(a); int y=find(b); p[x]=y; r[x]=(r[b]-r[a]+c+3)%3; } int err[NN]; void solve() { int a,b,c,J,cnt=0,last=0; memset(err,0,sizeof(err)); for (int k=1; k<=n; k++) { for (int i=1; i<=n; i++) { p[i]=i; r[i]=0; //0: the same 1: eat 2: be eated } for (int t=1; t<=m && !err[k]; t++) { a=e[t].a; b=e[t].b; c=e[t].c; if (a==k || b==k) continue; if (find(a)!=find(b)) Union(c,a,b); else if ((r[b]+c)%3!=r[a]) err[k]=t; } if (err[k]) { cnt++; last=max(last,err[k]); } else J=k; } if (cnt<n-1) printf("Can not determine\n"); else if (cnt==n) printf("Impossible\n"); else printf("Player %d can be determined to be the judge after %d lines\n",J-1,last); } int main() { int a,b; char ope; while (~scanf("%d%d",&n,&m)) { for (int i=1; i<=m; i++) { scanf("%d%c%d",&a,&ope,&b); a++,b++; if (ope=='=') e[i]=Rec(a,b,0); else if (ope=='>') e[i]=Rec(a,b,1); else e[i]=Rec(b,a,1); } solve(); } return 0; }