?

https://www.lydsy.com/JudgeOnline/problem.php?id=1823

https://www.luogu.org/problemnew/show/P4171

題面太長啦就不粘過來啦！

裸的2-SAT用來練板子的。

顯然屬于“a和b之間必須選一種”模型，只要a'向b連邊，b'向a連邊即可。

（被這題讀入坑了orz）

#include<cstdio> #include<queue> #include<cctype> #include<cstring> #include<cmath> #include<stack> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=1005; const int M=20005; struct node{int to,nxt; }e[M]; int T,n,m,head[N],cnt; int dfn[N],low[N],t,l; int to[N]; bool inq[N]; stack<int>q; inline int neg(int x){if(x>n)return x-n;return x+n; } inline void add(int u,int v){e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt; } void tarjan(int u){dfn[u]=low[u]=++t;q.push(u);inq[u]=1;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(inq[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){int v;l++;do{v=q.top();q.pop();inq[v]=0;to[v]=l;}while(u!=v);} } inline void init(){cnt=t=l=0;memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn)); } inline int get(){int k;char ch=0;while(ch!='m'&&ch!='h')ch=getchar();scanf("%d",&k);if(ch=='h')k+=n;return k; } int main(){scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a=get(),b=get();add(neg(a),b);add(neg(b),a);}for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);bool flag=1;for(int i=1;i<=n&&flag;i++){if(to[i]==to[i+n])flag=0;}if(flag)puts("GOOD");else puts("BAD");} }

+++++++++++++++++++++++++++++++++++++++++++

?+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

?+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

轉(zhuǎn)載于:https://www.cnblogs.com/luyouqi233/p/9022107.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1823：[JSOI2010]满汉全席——题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。