Hdu 4115 Eliminate the Conflict (2-sat 可行性判定)

- 日理万妓 2022-08-10 16:45 152阅读 0赞

题意：Bob和Alice玩剪刀石头布，一个玩n轮，Alice已经知道了Bob每次要出什么，1代表剪刀，2代表石头，3代表布，然后Bob对Alice作出了一些限制：

给m行，每行是a b k，如果k是0，表示Alice第a次和b次出的拳必须相同，如果k是1，表示Alice第a次和b次出的拳必须不相同。

一但Alice破坏了这个限制规则，或者输了一局，那么Alice就彻底输了。

问Alice可不可能赢？

思路：因为Alice一次都不能输，所以根据Bob出的拳，Alice只可以赢或者平局，即每次有两种选择，是2-SAT模型

然后会有一些矛盾对，假设第a次可以出a1，a2， 第b次可以出b1和b2

利用两元素不能同时取的模型建图,然后用2-SAT判断即可

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int MAXN = 10010;
    const int VN = MAXN*2;
    const int EN = VN*3;
    int n,m;
    
    struct Edge{
    	int v, next;
    };
    
    class Graph{
    public:
    	int head[VN],size;
    	Edge E[EN];
    	void init(){
    		size = 0;
    		memset(head, -1, sizeof(head));
    	}
    	void Add (int u,int v){
    		E[size].v = v;
    		E[size].next = head[u];
    		head[u] = size++;
    	}
    }g;
    
    class Two_Sat{
    public:
    	bool Check(const Graph&g, const int n){
    		SCC(g,n);
    		for (int i=0;i<n;i++)
    			if (belong[i*2] == belong[i*2+1])
    				return false;
    		return true;
    	}
    private:
    	int top, bcnt, idx;
    	int sta[VN],belong[VN];
    	int dfn[VN],low[VN];
    	bool inStack[VN];
    	
    	void targan (const Graph&g, const int u){
    		int v;
    		dfn[u] = low[u] = ++idx;
    		sta[top++] = u;
    		inStack[u] = true;
    		
    		for (int i=g.head[u]; i!=-1; i=g.E[i].next){
    			v = g.E[i].v;
    			if (dfn[v] < 0){
    				targan(g, v);
    				low[u] = min(low[u], low[v]);
    			}
    			else if(inStack[v])
    				low[u] = min(low[u], dfn[v]);
    		}
    		
    		if (dfn[u] == low[u]){
    			++bcnt;
    			do{
    				v = sta[--top];
    				inStack[v] = false;
    				belong[v] = bcnt;
    			}while(u != v);
    		}
    	}
    
    	void SCC (const Graph&g, int n){
    		top=bcnt=idx=0;
    		memset(dfn,-1,sizeof(dfn));
    		memset(low,0,sizeof(low));
    		memset(belong,0,sizeof(belong));
    		memset(inStack,false,sizeof(inStack));
    		for (int i=0; i<2*n;i++)
    			if (dfn[i] < 0) targan(g,i);
    	}
    }sat;
    
    int bob[MAXN];  
    int alice[MAXN][2];
    
    int main ()
    {
    	int T,i;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		g.init();  
    		scanf("%d%d",&n,&m);
    		for (i=0;i<n;i++)
    		{
    			scanf("%d",&bob[i]);
    			bob[i]--;  
    			alice[i][0]=bob[i];
    			alice[i][1]=(bob[i]+1)%3;
    		}
    		for (i=0;i<m;i++)
    		{
    			int a,b,k;
    			scanf("%d%d%d", &a,&b,&k);
    			a--,b--;
    			int u=a*2;
    			int v=b*2;
    			if (k)
    			{ // a,b不同
    				if (alice[a][0]==alice[b][0])
    					g.Add(u,v^1), g.Add(v,u^1);
    				if (alice[a][0]==alice[b][1])
    					g.Add(u,v), g.Add(v^1,u^1);
    				if (alice[a][1]==alice[b][0])
    					g.Add(u^1,v^1), g.Add(v,u);
    				if (alice[a][1]==alice[b][1])
    					g.Add(u^1,v), g.Add(v^1,u);
    			}
    			else
    			{ // a, b相同   
    				if (alice[a][0]!=alice[b][0])
    					g.Add(u,v^1), g.Add(v,u^1);
    				if (alice[a][0]!=alice[b][1])  
    					g.Add(u,v), g.Add(v^1,u^1);
    				if (alice[a][1]!=alice[b][0])  
    					g.Add(u^1,v^1), g.Add(v,u);
    				if (alice[a][1]!=alice[b][1])  
    					g.Add(u^1,v), g.Add(v^1,u);
    			}  
    		}  
    		printf("Case #%d: ",Cas);
    		if (sat.Check(g, n)) puts("yes");
    		else puts("no");
    	}
    	return 0;  
    }