题：http://acm.hdu.edu.cn/showproblem.php?pid=4115

题意：小明和小红玩猜拳游戏，已知小明的n个出拳情况，然后小明给出m种限制[x,y,c]若c==0，就要求小红第x局和第y局要出相同的方案，否则不同。问能否存在小红维持全部不输且符合这m个条件的情况；

分析：只用相同和不同情况，那么把2-SAT模型的x和x‘设为平和胜情况，判断4（2*2）种情况若要求相同时不同，则连边

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define pb push_back
const int M=22000;
int n,m;
vector<int>g[M],rg[M],cb;
int vis[M],cmp[M];
void py(int x){ printf("Case #%d: yes\n",x); }
void pn(int x){ printf("Case #%d: no\n",x); }
void init(){
    for(int i=0;i<=2*n;i++) g[i].clear(),rg[i].clear(),cmp[i]=0,vis[i]=0;
    cb.clear();
}
void addedge(int u,int v){

    g[u].pb(v);
    rg[v].pb(u);
}
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<(int)g[u].size();i++)if(!vis[g[u][i]]) dfs(g[u][i]);
    cb.pb(u);
}
void rdfs(int u,int k){
    vis[u]=1;
    cmp[u]=k;
    for(int i=0;i<(int)rg[u].size();i++)if(!vis[rg[u][i]]) rdfs(rg[u][i],k);

}
bool scc(){
    for(int i=0;i<2*n;i++)
        if(!vis[i])
            dfs(i);
    memset(vis,0,sizeof(vis));
    int k=0;
    for(int i=(int)cb.size()-1;i>=0;i--) if(!vis[cb[i]]) rdfs(cb[i],++k);

    for(int i=0;i<n;i++)
        if(cmp[2*i]==cmp[2*i+1])return false;
    return true;
}
int beat[]={0,2,3,1};
int a[M];
int main(){
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i<n;i++){
            scanf("%d",&a[2*i]);
            a[2*i+1]=beat[a[2*i]];
        }
        int flag=0;
        while(m--){
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            x--,y--;
            if(x==y&&c==1){
                flag=1;
            }
            if(c==0){///要相同
                if(a[2*x]!=a[2*y]){///平!=平
                    addedge(2*x,2*y+1);
                    addedge(2*y,2*x+1);
                }
                if(a[2*x]!=a[2*y+1]){///平!=胜
                    addedge(2*x,2*y);
                    addedge(2*y+1,2*x+1);
                }
                if(a[2*x+1]!=a[2*y]){///胜!=平
                    addedge(2*x+1,2*y+1);
                    addedge(2*y,2*x);
                }
                if(a[2*x+1]!=a[2*y+1]){///胜!=胜
                    addedge(2*x+1,2*y);
                    addedge(2*y+1,2*x);
                }
            }
            else{///要不同
                if(a[2*x]==a[2*y]){///平==平
                    addedge(2*x,2*y+1);
                    addedge(2*y,2*x+1);
                }
                if(a[2*x]==a[2*y+1]){///平==胜
                    addedge(2*x,2*y);
                    addedge(2*y+1,2*x+1);
                }
                if(a[2*x+1]==a[2*y]){///胜==平
                    addedge(2*x+1,2*y+1);
                    addedge(2*y,2*x);
                }
                if(a[2*x+1]==a[2*y+1]){///胜==胜
                    addedge(2*x+1,2*y);
                    addedge(2*y+1,2*x);
                }
            }
        }
        if(flag||!scc()) pn(cas);
        else py(cas);
    }
    return 0;
}

View Code