思路：将每个回合的平手和赢最为一对对立状态。那么后面就是2-SAT判断了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<map> #define Maxn 20010 using namespace std; map<int ,int> g[Maxn]; int vi[Maxn],head[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,id[Maxn],Stack[Maxn],wh[Maxn],hh[4][4]; struct Edge{ int u,v,next; }edge[100000]; void init()//初始化 { memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(id,0,sizeof(id)); for(int i=0;i<Maxn;i++) g[i].clear(); e=lab=top=num=0; } void add(int u,int v)//加边 { edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } void Tarjan(int u)//找出强连通分支 { int i,j,v; dfn[u]=low[u]=++lab; Stack[top++]=u; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++num; do{ i=Stack[--top]; vi[i]=0; id[i]=num; }while(i!=u); } } int solve() { int i,j; for(i=1;i<=n;i++) if(!dfn[i]) Tarjan(i); for(i=1;i<=n;i++) if(id[i]==id[i+n]) return 0; return 1; } int main() { int t,i,j,m,u,v,k,Case=0; hh[1][2]=hh[2][3]=hh[3][1]=1; scanf("%d",&t); while(t--){ init(); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",wh+i); int f=0; for(i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&k); if(u>v) swap(u,v); if(g[u][v]==k+1||u==v&&k==0) continue; if(g[u][v]&&g[u][v]!=k+1||u==v&&k==1) {f=1;break;} g[u][v]=k+1; if(k==0){ if(wh[u]==wh[v]){ add(u,v); add(v+n,u+n); add(v,u); add(u+n,v+n); }else if(hh[wh[u]][wh[v]]){ add(u,v+n); add(v,u+n); add(u+n,v); add(v+n,u); add(u+n,v+n); add(v,u); } else { add(u,v+n); add(v,u+n); add(u+n,v); add(v+n,u); add(u,v); add(v+n,u+n); } } else{ if(wh[u]==wh[v]){ add(u,v+n); add(v,u+n); add(u+n,v); add(v+n,u); }else if(hh[wh[u]][wh[v]]){ add(u,v); add(v+n,u+n); } else{ add(u+n,v+n); add(v,u); } } } printf("Case #%d: ",++Case); if(f){ for(i++;i<=m;i++){ scanf("%d%d%d",&u,&v,&k); } printf("no "); continue; } if(solve()) printf("yes "); else printf("no "); } return 0; }