codeforces776D The Door Problem

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

题目链接：CF776D

正解：$2-SAT$

解题报告：

　　似乎以前做过类似的题啊，不过因为没有正好$2$个这个限制所以并不好做。

　　考虑题目相当于是问是否存在使得每个点都变成$0$的的方案，一次操作我们可以看成是一次异或。

　　因为有一个强有力的限制条件，我们就可以直接往$2-SAT$模型上靠了。　　

　　当$r[i]$初值为$1$，那么需要$0$次或$2$次操作；否则需要恰好一次操作。

　　那么这个题的$2-SAT$模型就是控制每扇门的钥匙是否选择的异或值恰好等于$r[i]$，直接建图跑$2-SAT$就好了。

//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <ctime>
using namespace std;
typedef long long LL;
const int MAXN = 200011;
const int MAXM = 2000011;
int n,m,X[MAXN];
vector<int>w[MAXN];
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}

namespace SAT_2{
	int ecnt,first[MAXN],to[MAXM],next[MAXM],top,stack[MAXN],bel[MAXN],scnt,dfn[MAXN],low[MAXN];
	bool pd[MAXN];
	inline void link(int x,int y){ 
		next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; 
	}
	inline void tarjan(int x){
		dfn[x]=low[x]=++ecnt;
		pd[x]=1; stack[++top]=x;
		for(int i=first[x];i;i=next[i]) {
			int v=to[i];
			if(!dfn[v]) {
				tarjan(v);
				low[x]=min(low[x],low[v]);
			}
			else if(pd[v]) low[x]=min(low[x],low[v]);
		}
		if(dfn[x]==low[x]) {
			scnt++;
			while(stack[top]!=x) {
				bel[stack[top]]=x; pd[x]=0;
				top--;
			}
			pd[x]=0; bel[x]=scnt;
			top--;
		}
	}

	inline void work(){
		ecnt=0;
		for(int i=2;i<=(m<<1)+1;i++) if(!dfn[i]) tarjan(i);
		for(int i=1;i<=m;i++) if(bel[i<<1]==bel[i<<1|1]) { puts("NO"); return ; }
		puts("YES");
	}
}

inline void work(){
	using namespace SAT_2;
	n=getint(); m=getint(); int x,y;
	for(int i=1;i<=n;i++) X[i]=getint();
	for(int i=1;i<=m;i++) {
		x=getint();
		while(x--) {
			y=getint();
			w[y].push_back(i);
		}
	}

	for(int i=1;i<=n;i++) {
		x=w[i][0]; y=w[i][1]; 
		x<<=1; y<<=1;
		if(X[i]==0) {
			link(x,y|1); link(y|1,x);
			link(x|1,y); link(y,x|1);
		}
		else {
			link(x,y); link(y,x);
			link(x|1,y|1); link(y|1,x|1);
		}
	}

	SAT_2::work();
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("776.in","r",stdin);
	freopen("776.out","w",stdout);
#endif
    work();
    return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。