本文主要是介绍处女座与宝藏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
处女座进行了一次探险，发现了一批宝藏。如果他获得这批宝藏，那么他一辈子都不需要工作了。但是处女座遇到了一个难题。
宝藏被装在n个宝箱里，宝箱编号为1,2,…,n，只有所有宝箱在某一时间被打开，处女座才能获得宝藏。有m个开关，每个开关控制k个宝箱，如果按下一个开关，那么这k个宝箱的开关状态都会发生改变（从开启变成关闭，从关闭变成开启），处女座想知道他能否获得这批宝藏。
【输入描述】
第一行两个正整数n,m，
第二行n个整数，每个整数为0或1，表示初始时宝箱的状态，0表示开启，1表示关闭
接下来m行，每行开头一个整数k表示这个开关控制的宝箱的个数，接下来k个整数，表示控制宝箱的编号
1<=n,m<=200000
1<=k<=n
题目保证每个宝箱最多被两个开关控制。
【输出描述】
一行，如果处女座能获得宝藏，输出”YES”，否则输出”NO”
【样例】
示例1
输入
4 4
1 0 1 1
2 3 4
2 1 3
1 2
2 1 2
输出
YES
思路：2-SAT
每个开关有两种状态，按或不按，并且两者一旦选择其中一种，那么就一定要选择其他开关的状态使得宝藏开启，可以发现，宝藏其实是用来建边的
由于每个锁最多被 k 个开关控制，因此可以对没有控制的锁直接进行判断：
- 被一个开关控制的锁：取 1 或取 0
- 被两个开关控制的锁：取 00 或取 11 或取 01 或取 10
根据 m 个限制条件进行建图，建图完成后 Tarjan 缩点，然后判断两个对立的点是否在同一个块中，若在同一个块则无解，反之则有解
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define N 1000001
#define LL long long
using namespace std;struct Edge{int to,next;
}edge[N];
int head[N],cnt;
int n,m;
int a[N];
vector<int> G[N];
int low[N],dfn[N],belong[N];
int time_block;
int scc;
int Stack[N],top;
bool vis[N];
int num[N];void Tarjan(int u){low[u]=dfn[u]=++time_block;Stack[top++]=u;vis[u]=true;int v;for(int i=head[u];i != -1;i = edge[i].next){v=edge[i].to;if(!dfn[v]){Tarjan(v);if(low[u]>low[v])low[u]=low[v];}else if(vis[v]&&low[u]>dfn[v])low[u]=dfn[v];}if(low[u]==dfn[u]){scc++;do{v=Stack[--top];vis[v]=false;belong[v]=scc;num[scc]++;}while(v!=u);}
}
void addEdge(int next,int to){//添边edge[cnt].to=to;edge[cnt].next=head[next];head[next]=cnt++;
}
int main(){memset(head,-1,sizeof(head));cnt=0;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){int k;cin>>k;for(int j=1;j<=k;j++){int x;cin>>x;G[x].push_back(i);}}for(int i=1;i<=n;i++){int len=G[i].size();if(len==0){//初始条件if(a[i]==1){addEdge(0,0);addEdge(1,1);}}else if(len==1){//被一个锁控制int temp=G[i][0]<<1;if(a[i]==1)addEdge(temp,temp^1);elseaddEdge(temp^1,temp);}else if(len==2){//被两个锁控制int x=G[i][0]<<1;int y=G[i][1]<<1;if(a[i]==1){addEdge(x,y^1);addEdge(y,x^1);addEdge(x^1,y);addEdge(y^1,x);}else{addEdge(x,y);addEdge(y,x);addEdge(x^1,y^1);addEdge(y^1,x^1);}}}memset(dfn,0,sizeof(dfn));memset(vis,false,sizeof(vis));memset(num,0,sizeof(num));time_block=0;scc=top=0;for(int i=0;i<(m<<1);i++)if(!dfn[i])Tarjan(i);bool flag=true;for(int i=0;i<(m<<1);i+=2)if(belong[i]==belong[i^1])//判断是否在同一个块中flag=false;if(flag)printf("YES\n");elseprintf("NO\n");return 0;
}
这篇关于处女座与宝藏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
