POJ 3648 Wedding(2
POJ 3648 Wedding(2-SAT) http://poj.org/problem?id=3648 题意: 有一对新人结婚,n-1对夫妇去参加婚.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时
POJ 3648 Wedding(2-SAT)
http://poj.org/problem?id=3648
题意:
有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例,输出应该坐在新娘同一边的人编号。
分析:
由于有n对夫妇(0号表示新婚夫妻).所以我们这里用0表示第0对的妻子,1表示第0对的丈夫. 2*i表示第i对的夫人,2*i+1表示第i对的丈夫.一共就有2*n个人了.
然后对于每个人来说,把他分成两个节点,如果该人在做左边就mark[i*2],如果该人坐右边就mark[i*2+1].
我令新娘直接坐左边即第0个人mark[0]=true,新郎直接坐右边即第1个人mark[1*2+1]=true.
然后对于每对夫妻,因为他们不能在同一边,所以第i对夫妻中a= 2*i表示妻子,b=2*i+1表丈夫. 有这样的关系:
a在左边,那么b就在右边,a*2->b*2+1
a在右边,那么b就在左边,a*2+1->b*2
b在左边,那么a就在右边,b*2->a*2+1
b在右边,那么a就在左边,b*2+1->a*2
然后对于每对有奸情的人a与b,因为它们不能同时在新娘对面(右边),所以:
a*2+1->b*2
b*2+1->a*2
注意首先我们定了新娘(0号)在左边,新郎(第1号人)一定在右边,所以我们要先加上:
0*2+1->0*2 和 1*2->1*2+1
这样就保证了新娘和新郎在固定的那边不动.
AC代码:
#include#include #include #include using namespace std; const int maxn = 1000*2+100; struct TwoSAT { int n; vector G[maxn*2]; int S[maxn*2],c; bool mark[maxn*2]; bool dfs(int x) { if(mark[x^1]) return false; if(mark[x]) return true; mark[x]=true; S[c++]=x; for(int i=0;i n=n; for(int i=0;i0) mark[S[--c]]=false; if(!dfs(i+1)) return false; //注意细节,这里写成了return true; } } return true; } }TS; int main() { int n,m; while(scanf("%d%d",&n,&m)==2) { if(n==0&&m==0) break; TS.init(n*2); TS.add_clause(0,1,0,0);//新娘放左 TS.add_clause(1,0,1,1);//新郎放右 for(int i=1;i
推荐阅读
-
No.2 广度优先遍历BFS下的捉住那头牛。POJ-3278
-
CSUFT 个人赛(2) C题(POJ - 1316) D题(HDU - 2076) G题(HihoCoder - 1740) H题(HDU - 5640)
-
POJ3683 Priest John's Busiest Day(2-SAT)
-
POJ 3207 Ikki's Story IV - Panda's Trick(2-SAT)
-
POJ 3648 Wedding (2-SAT强连通缩点法+拓扑排序任意解)
-
全网唯一真题解 POJ 3648 2-SAT
-
poj_3628 Bookshelf 2
-
POJ 3648 Wedding(2
-
2-sat 学习日记 + 例题(洛谷p4782 + poj3678 + poj3683)
-
[2-sat专练]poj 3683,hdu 1814,hdu 1824,hdu 3622,hdu 4115,hdu 4421