The Door Problem CodeForces - 776D 并查集||染色法||2-sat

傳送門：CodeForces - 776D

題意：有n個門和m個開關，每個門由兩個開關控制，每個開關可以控制任意多個門，問能否通過操作某些開關使得所有門都打開。（給出門的初始狀态）

思路：明明有那麼多解法，卻一個也想不到。。。先分析一下題目，大部分開關問題首先要想到的一點就是任何開關操作兩次以上都是無意義的，是以對于每個開關，我們要麼操作一次，要麼不操作，對于控制的門初始狀态為1的兩個開關，我們要麼兩個都操作，要麼兩個都不操作，這樣才能保證門的末狀态為1，而控制的門初始狀态為0的兩個開關，我們隻能而且必須操作其中一個。

有了上面的分析，我們考慮用并查集維護開關之間的關系，因為每個開關有操作和不操作兩種狀态，是以，我們要把每個點拆成兩個點，i表示第i個開關沒操作過，i+m表示第i個開關操作過，若第i個門初始狀态為1，控制開關為a和b，則合并a，b和

a+m，b+m。

若初始狀态為0，則合并a，b+m和b，a+m。最後判斷一下如果存在i和i+m在同一個集合中則說明出現了沖突。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
using namespace std;
typedef pair<int,int>P;
const int MAXN=100010;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int door[2*MAXN];
vector<int>v[2*MAXN];
int f[MAXN*3];
int getf(int k)
{
	return k==f[k]?k:f[k]=getf(f[k]);
}
void merge(int a,int b)
{
	a=getf(a);
	b=getf(b);
	if(a!=b)
	f[a]=b;
}
int main()
{
	std::ios::sync_with_stdio(0);
	int n,m,k,t;
	cin>>n>>m;
	for(int i=0;i<=m*2;i++)
	f[i]=i;
	for(int i=1;i<=n;i++)
	cin>>door[i];
	for(int i=1;i<=m;i++)
	{
		cin>>k;
		while(k--)
		{
			cin>>t;
			v[t].push_back(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(door[i])
		{
			merge(v[i][0],v[i][1]);
			merge(v[i][0]+m,v[i][1]+m);
		}
		else
		{
			merge(v[i][0],v[i][1]+m);
			merge(v[i][0]+m,v[i][1]);
		}
	}
	for(int i=1;i<=m;i++)
	if(getf(i)==getf(i+m))
	{
		cout<<"NO\n";
		return 0;
	}
	cout<<"YES\n";
 	return 0;
}
           

然後說一下染色法，對于每個門的兩個開關建邊，權值為門的初始狀态，這樣建圖就有一點二分圖的意思了，然後dfs對每個點染色，若邊權為1，則端點顔色應該相同，邊權為0則端點顔色不同。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep(i,x,n) for(int i=x;i<n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
using namespace std;
typedef pair<int,int>P;
const int MAXN=100010;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int door[2*MAXN],clr[MAXN];
vector<int>v[2*MAXN];
vector<P>mp[MAXN];
bool dfs(int u,int c)
{
	if(clr[u])
	{
		if(clr[u]!=c)
		return false;
		return true;
	}
	clr[u]=c;
	for(int i=0;i<mp[u].size();i++)
	{
		int v=mp[u][i].first;
		if(mp[u][i].second)
		{
			if(!dfs(v,c))
			return false;
		}
		else
		{
			if(!dfs(v,-c))
			return false;
		}
	}
	return true;
}
int main()
{
	std::ios::sync_with_stdio(0);
	int n,m,k,t;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>door[i];
	for(int i=1;i<=m;i++)
	{
		cin>>k;
		while(k--)
		{
			cin>>t;
			v[t].push_back(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		mp[v[i][0]].push_back(P(v[i][1],door[i]));
		mp[v[i][1]].push_back(P(v[i][0],door[i]));
	}
	for(int i=1;i<=m;i++)
	{
		if(!clr[i])
		{
			if(!dfs(i,1))
			{
				cout<<"NO\n";
				return 0;
			}
		}
	}
	cout<<"YES\n";
 	return 0;
}
           

這題好像還是2-sat模闆題，不過蒟蒻還沒來得及學2-sat。。等學了再補一發吧。。