bzoj 1283(2-sat)

bzoj 1283(2-sat)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说bzoj 1283(2-sat),希望能够帮助大家进步!!!

传送门

题意:

\(n\)种菜,每种菜有两个风格:汉式或满式。现在有\(m\)个评委,第\(i\)评委都会有两种喜欢的风味,即(汉式/满式)菜\(a_i\),你只要做出其中一种符合第\(i\)个评委喜欢的风味就算你通过了他的评判。你要赢需要获得所有评委的通过。现在问你,假设你做出的菜款式是任意的,你有机会获胜吗。

分析:

我们发现,对于每一种菜,都会有两种的状态:汉式和满式;即倘若我们选取了汉式的风格,那么必定不能选择满式的风格。因此我们可以将汉式作为\(0\)状态,满式作为\(1\)状态,而现在要通过第\(i\)个评委的审核,只需要满足其中的一种条件即可,故这是一个或的关系。

如此一来,这个问题就可以转化成一个或的\(2-sat\)的问题,对于每一个菜,我们令\(2*i+1\)作为\(1\)状态,\(2*i\)作为\(0\)状态;之后按照或的\(2-sat\)进行建图即可。

代码:

#include <bits/stdc++.h> #define maxn 20050 using namespace std; struct Node{ int to,next; }q[maxn]; int head[maxn],cnt=0,st[maxn],top=0; bool vis[maxn]; void add_edge(int from,int to){ q[cnt].to=to; q[cnt].next=head[from]; head[from]=cnt++; } void init(){ memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); cnt=0,top=0; } bool dfs(int x){ if(vis[x^1]) return false; if(vis[x]) return true; vis[x]=1; st[++top]=x; for(int i=head[x];i!=-1;i=q[i].next){ int to=q[i].to; if(!dfs(to)) return false; } return true; } bool Towsat(int n){ for(int i=0;i<n;i+=2){ if(!vis[i]&&!vis[i^1]){ top=0; if(!dfs(i)){ while(top) vis[st[top--]]=0; if(!dfs(i^1)) return false; } } } return true; } int main() { int t; scanf("%d",&t); while(t--){ int n,m; init(); scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ char str1,str2; int num1,num2; getchar(); scanf("%c%d %c%d",&str1,&num1,&str2,&num2); //cout<<str1<<" "<<num1<<" "<<str2<<" "<<num2<<endl; int x=2*(num1)+ (str1=='h'?1:0); int y=2*(num2)+ (str2=='h'?1:0); add_edge(x^1,y); add_edge(y^1,x); } if(Towsat(2*n)) puts("GOOD"); else puts("BAD"); } return 0; } 

转载于:https://www.cnblogs.com/Chen-Jr/p/11158368.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29688

发表评论