Codeforces 776D：The Door Problem（并查集/2-SAT）

题意
- 给你n扇门，m种操作，n扇门开始的状态，0代表关，1代表开
- m个操作，每个操作会使k扇门翻转，问能不能将所有门打开。
- PS:每扇门都严格有两种操作包含它。
题解
- 2-SAT经典问题，但是我不会，所以用并查集
- 假设一个门的操作是a和b。令k代表是使用k操作，k+m表示不用。
  - 当第i扇门关着，用a和b+m或者a+m和b。(即将其合并入并查集)
  - 如果是开着，用a和b或者a+m和b+m。
- 用并查集维护，最后判断一下i和i+m是不是在一个并查集，如果是，那就矛盾，NO。
- PS：这里的并查集维护的是翻转的操作，所以每次需要对m*2的pre数组进行初始化
- 总结：其实这类”程序自动分析“式题目，大多可以用并查集+连通块解决，我们需要找到题目中的”等价关系“（连通块），”边权关系“（连通块之间），以及”矛盾关系“（连通块内部以及连通块外部）
- 拿这题来说，”等价关系“就是门对应的指令状态，”矛盾关系“为连通块内部矛盾，而由于这题只有是否等价而没有大小关系，所以没有”边权关系“

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<fstream>
#include<algorithm>
using namespace std;

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define CLR(a) memset(a,0,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const int maxn=2e5+10;
vector<int>sp[maxn];
int pre[maxn*2],init[maxn];
int find(int x){  
    return x==pre[x]?x:pre[x]=find(pre[x]); 
}
void Union(int a,int b){
	if(find(a)!=find(b))pre[find(a)]=find(b);
}
int main(){
	int x,y,n,m,i,j;
	scanf("%d%d",&n,&m);
	rep(i,1,n)scanf("%d",&init[i]);
	rep(i,1,m){
		scanf("%d",&x);
		rep(j,1,x){
			scanf("%d",&y);
			sp[y].push_back(i);
		}
	}
	rep(i,1,m*2)pre[i]=i;
	for(i=1;i<=n;i++){
		int a=sp[i][0],b=sp[i][1];
		if(!init[i]){
			Union(a,b+m);
			Union(a+m,b);
		}
		else{
			Union(a,b);
			Union(a+m,b+m);
		}
	}
	rep(i,1,m){
		if(find(i)==find(i+m)){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}

发表评论 取消回复

发表评论取消回复