浅谈2—SAT问题

浅谈2—SAT问题

2-SAT:

1    2  -  SAT就是2判定性问题,是一种特殊的逻辑判定问题。
2    2  -  SAT问题有何特殊性?该如何求解?
3  我们从一道例题来认识2  -  SAT问题,并提出对一类2  -  SAT问题通用的解法。
4 
  Poi   0106   Peaceful Commission [和平委员会]:

某国有n个党派,每个党派在议会中恰有2个代表。
现在要成立和平委员会 ,该会满足:
每个党派在和平委员会中有且只有一个代表 
如果某两个代表不和,则他们不能都属于委员会 
代表的编号从1到2n,编号为2a
  -  1  、2a的代表属于第a个党派
  输入n(党派数),m(不友好对数)及m对两两不和的代表编号 
其中1≤n≤
  8000    0  ≤m ≤  20000   

求和平委员会是否能创立。若能,求一种构成方式。 
输入:     输出:
  3     2           1          
  1     3           4            
  2     4           5                    

  原题可描述为:

有n个组,第i个组里有两个节点Ai, Ai
  '   。需要从每个组中选出一个。而某些点不可以同时选出(称之为不相容)。任务是保证选出的n个点都能两两相容。 
 

(在这里把Ai, Ai
  '   的定义稍稍放宽一些,它们同时表示属于同一个组的两个节点。也就是说,如果我们描述Ai,那么描述这个组的另一个节点就可以用Ai  ' 
  初步构图
如果Ai与Aj不相容,那么如果选择了Ai,必须选择Aj‘ ;同样,如果选择了Aj,就必须选择Ai’ 。
   Ai             Aj
  '
     Aj             Ai‘                        
这样的两条边对称

  我们从一个例子来看:
假设4个组,不和的代表为:1和4,2和3,7和3,那么构图:
假设:首先选1 3必须选,2不可选 8必须选,
  4  、7不可选   5  、6可以任选一个

 
  矛盾的情况为:
存在Ai,使得Ai既必须被选又不可选。
 
得到算法1:
枚举每一对尚未确定的Ai, Ai‘ ,任选1个,推导出相关的组,若不矛盾,则可选择;否则选另1个,同样推导。若矛盾,问题必定无解。
此算法正确性简要说明:
由于Ai,Ai
  '   都是尚未确定的,它们不与之前的组相关联,前面的选择不会影响Ai, Ai  '   。

算法的时间复杂度在最坏的情况下为O(nm)。
在这个算法中,并没有很好的利用图中边的对称性
  更一般的说:
在每个一个环里,任意一个点的选择代表将要选择此环里的每一个点。不妨把环收缩成一个子节点(规定这样的环是极大强连通子图)。新节点的选择表示选择这个节点所对应的环中的每一个节点.
对于原图中的每条边Ai
  ->  Aj(设Ai属于环Si,Aj属于环Sj)如果Si≠Sj,则在新图中连边:Si  -> Sj

这样构造出一个新的有向无环图。
此图与原图等价。
  通过求强连通分量,可以把图转换成新的有向无环图,在这个基础上,介绍一个新的算法。

新算法中,如果存在一对Ai, Ai
  '  属于同一个环,则判无解,否则将采用拓扑排序,以自底向上的顺序进行推导,一定能找到可行解。 
 

至于这个算法的得来及正确性,将在下一段文字中进行详细分析。

回忆构图的过程:
对于两个不相容的点 Ai, Aj,构图方式为:Ai
  ->  Aj  '  ,Aj->Ai  '  ,前面提到过,这样的两条边对称,也就是说:
如果存在Ai
  ->  Aj,必定存在Aj  '  ->Ai  ' 

等价于:Ai
  ->  Ak,Ak  '  ->Ai  '   方便起见,之后“  ->  ”代表这样一种传递关系.


  猜测1:图中的环分别对称
如果存在Ai,Aj,Ai,Aj属于同一个环(记作Si),那么Ai
  '  , Aj  '  也必定属于一个环(记作Si  '  ). 
 
再根据前面的引理,不难推断出每个环分别对称。 

证明方式与引理相类似
一个稍稍复杂点的结构,其中红、蓝色部分分别为两组对称的链结构
推广2:对于任意一对Si, Si
  '   ,Si的后代节点与Si  '   的前代节点相互对称。 
继而提出:
猜测2:若问题无解,则必然存在Ai, Ai
  '   ,使得Ai,Ai  '  属于同一个环。也就是,如果每一对Ai,Ai  '   都不属于同一个环,问题必定有解。下面给出简略证明: 
  先提出一个跟算法1相似的步骤: 
如果选择Si,那么对于所有Si
  ->  Sj,Sj都必须被选择。 
而Si
  '   必定不可选,这样Si’的所有前代节点也必定不可选(将这一过程称之为删除)。 
 
由推广2可以得到,这样的删除不会导致矛盾。

假设选择S3
  '    
 
选择S3  '  的后代节点, S1  ' 
删除S3
删除S3的前代节点S1
S1与S1
  '  是对称的 
 

每次找到一个未被确定的Si,使得不存在Si
  ->  Si  '   选择Si及其后代节点而删除Si’及Si‘的前代节点。一定可以构造出一组可行解。 
 
因此猜测2成立。

另外,若每次盲目的去找一个未被确定的Si,时间复杂度相当高。
以自底向上的顺序进行选择、删除,这样还可以免去“选择Si的后代节点”这一步。
用拓扑排序实现自底向上的顺序。

一组可能的拓扑序列(自底向上):S1
  '  ,S2,S2  '  ,S3  '  ,S3,S1 
 

算法2的流程: 

  1  .构图
  2  .求图的极大强连通子图
  3  .把每个子图收缩成单个节点,根据原图关系构造一个有向无环图
  4  .判断是否有解,无解则输出(退出)
  5  .对新图进行拓扑排序
  6  .自底向上进行选择、删除
  7  .输出

小结:
整个算法的时间复杂度大概是O(m),解决此问题可以说是相当有效了。
在整个算法的构造、证明中反复提到了一个词:对称。发现、利用了这个图的特殊性质,我们才能够很好的解决问题。
并且,由2
  -  SAT问题模型变换出的类似的题目都可以用上述方法解决。 

全文总结:
充分挖掘图的性质,能够更好的解决问题。
不仅仅是对于图论,这种思想可以在很多问题中得到很好的应用。
希望我们能掌握此种解题的思想,在熟练基础算法的同时深入分析、灵活运用、大胆创新,从而解决更多更新的难题。

2-sat问题

Implication_graph

在这篇文章我们提到过sat问题,sat问题是第一个npc问题,具体是这样的SAT全称是satisfiability,他是问对于一个合取范式,是否有一种输入使得他的输出是1,具体点就是类似这样的布尔表达式(x1 or x2 or x3)and(x3 or x4)and(not x1 or x5)对于所有的x是否有一种01取值,使得最后的结果是1。而2-sat问题就是每一个由or连接的子式都只包含两个变量,比如这样(x1 or x2) and (not x3 or x1),2-sat问题是有多项式解法的,而3-sat就是npc问题了,前段时间有人宣称证明了p=np就是因为他自己找到了3-sat的多项式解法,当然最后被证明解法是错误的。。。那么对于2-sat问题解法而言,经典的就是利用强连通分支的算法来解决,最近上的coursera上的algo2有个随机算法也很有趣这里我们也要讲一下。

先来看经典的利用强连通分支的图论解法。我们把每个变量x都拆成2个点,两个点x和~x分别表示这个点取1和这个点取0,所以最后我们就是在这2n个点中选择满足要求的n个点。对于每个子式,假设子式是(x1 or x2),对于2-sat问题而言我们需要每个子式都得1,也就是对于这个子式而言,x1和x2至少要取一个,对应于图中就是,如果我们取~x1就必须取x2,取~x2就必须取x1,所以我们就在图中从~x1到x2和从~x2到x1连两条有向边。同样的如果子式中有not也是类似方法,比如(not x1 or x2)那么就是X1到x2和~x2到~x1两条有向边。一开始的图片构成的图表示的这个式子。

(x0x2)(x0¬x3)(x1¬x3)(x1¬x4)(x2¬x4)(x0¬x5)
(x1¬x5)(x2¬x5)(x3x6)(x4x6)(x5x6)

构建好图之后对图求强连通分支,很显然的如果xi和~xi在同一个强连通分支中那么就是不存在解的。之后进行染色判定,强连通分支缩点之后,把所有的边反向,然后按照拓扑排序的顺序遍历节点,如果节点没有被染色,就涂成红色,然后把和这个点互斥的点(所谓互斥的点就是如果x和~x所在的点),以及这个点的子孙都涂成蓝色,这样取出红色的点就是满足条件的解。这里就不证明了,详细的可以看伍昱的《由对称性解2-SAT问题》和赵爽的《2-SAT解法浅析》两篇。看证明的时候注意对称性,就是说如果x,y在同一个连通分支,那么~x,~y也在同一个连通分支,如果x到y有路,那么~y到~x也有路,注意这个对称性的特点的话,那两篇文章里的证明也就不难看懂了。

talk is easy,show me the code,那么让我们看一下代码吧,这里就用poj 3648来举例。

  1. #include <cstdio>
  2. #include <cstring>
  3. const  int maxn = 10010;
  4. int n, m, nxt [maxn ], head [maxn ], pnt [maxn ], ne, e, a, b, a0, b0;
  5. char c1, c2;
  6. int nnxt [maxn ], nhead [maxn ], npnt [maxn ];
  7. int order [maxn ], norder, id [maxn ], v [maxn ];
  8. int ans [maxn ], op [maxn ];
  9. void dfs ( int d ) {
  10. v [d ]  =  1;
  11. for ( int i =head [d ]; i != -1; i =nxt [i ] )
  12. if ( !v [pnt [i ] ] )
  13. dfs (pnt [i ] );
  14. order [norder ++ ]  = d;
  15. }
  16. void ndfs ( int d,  int k ) {
  17. v [d ]  =  1;
  18. id [d ]  = k;
  19. for ( int i =nhead [d ]; i != -1; i =nnxt [i ] )
  20. if ( !v [npnt [i ] ] )
  21. ndfs (npnt [i ], k );
  22. }
  23. void addedge ( int s,  int t ) {
  24. pnt [e ]  = t; nxt [e ]  = head [s ]; head [s ]  = e ++;
  25. }
  26. void addnedge ( int t,  int s ) {
  27. npnt [ne ]  = s; nnxt [ne ]  = nhead [t ]; nhead [t ]  = ne ++;
  28. }
  29. void color ( int d ) {
  30. ans [d ]  =  2;
  31. for ( int i =head [d ]; i != -1; i =nxt [i ] )
  32. if ( !ans [pnt [i ] ] )
  33. color (pnt [i ] );
  34. }
  35. int main ( ) {
  36. while ( 1 ) {
  37. norder  = e  = ne  =  0;
  38. memset (head,  -1sizeof head );
  39. memset (nhead,  -1sizeof nhead );
  40. scanf ( "%d%d"&n,  &m );
  41. if ( !n &&!m )
  42. break;
  43. for ( int i = 0; i<m;  ++i ) {
  44. scanf ( "%d%c%d%c"&a,  &c1,  &b,  &c2 );
  45. if (c1 == 'h' )
  46. a0  = n +a;
  47. else {
  48. a0  = a;
  49. += n;
  50. }
  51. if (c2 == 'h' )
  52. b0  = n +b;
  53. else {
  54. b0  = b;
  55. += n;
  56. }
  57. addedge (a0, b );
  58. addnedge (b, a0 );
  59. addedge (b0, a );
  60. addnedge (a, b0 );
  61. }
  62. addedge ( 0, n );
  63. addnedge (n,  0 );
  64. memset (v,  0sizeof v );
  65. for ( int i = 0; i< 2 *n;  ++i )
  66. if ( !v [i ] )
  67. dfs (i );
  68. int k = 0;
  69. memset (v,  0sizeof v );
  70. memset (id,  -1sizeof id );
  71. for ( int i =norder -1; i> = 0--i )
  72. if ( !v [order [i ] ] )
  73. ndfs (order [i ], k ++ );
  74. int mark  =  1;
  75. for ( int i = 0; i<n;  ++i )
  76. if (id [i ] ==id [i +n ] )
  77. mark  =  0;
  78. if ( !mark ) {
  79. printf ( "bad luck\n" );
  80. continue;
  81. }
  82. for ( int i = 0; i<n;  ++i ) {
  83. op [id [i ] ]  = id [i +n ];
  84. op [id [i +n ] ]  = id [i ];
  85. }
  86. = norder  =  0;
  87. memset (head,  -1sizeof head );
  88. memset (v,  0sizeof v );
  89. memset (ans,  0sizeof ans );
  90. for ( int i = 0; i<n;  ++i )
  91. for ( int j =nhead [i ]; j != -1; j =nnxt [j ] )
  92. addedge (id [i ], id [npnt [j ] ] );
  93. for ( int i = 0; i<k;  ++i )
  94. if ( !v [i ] )
  95. dfs (i );
  96. for ( int i =norder -1; i> = 0--i )
  97. if ( !ans [order [i ] ] ) {
  98. ans [order [i ] ]  =  1;
  99. color (op [order [i ] ] );
  100. }
  101. for ( int i = 1; i<n;  ++i ) {
  102. if (ans [id [i ] ]  ==  1 )
  103. printf ( "%dh", i );
  104. else
  105. printf ( "%dw", i );
  106. if (i<n -1 )
  107. printf ( " " );
  108. else
  109. printf ( "\n" );
  110. }
  111. }
  112. return  0;
  113. }

代码自我感觉还是比较清晰的就不解释了,整个过程就是按照上面说的算法进行的。ok,到这里而言acmer的内容已经足够了,下面我们来说说algo2里提到的随机算法。

在讲随机算法之前,首先要介绍“random walks on a line”,假设我们在数轴的点0的位置,在点0的话,下一个时刻我们会移动到点1上,如果在其他的点x,我们有50%的概率下一个时刻移动到点x-1上,有50%的概率移动到x+1上。现在让我们来算一下,从点0开始移动到点n,期望需要移动多少步。这个期望的算法和之前写的这篇的方法差不多。设E(i)是从点i(i<=n)移动到点n所需要的期望的步数。于是我们有

E(n)=0
E(0)=E(1)+1
E(i)=0.5(1+E(i+1))+0.5(1+E(i1))

有上面的式子我们可以得到最后的结果,推导比较简单,就不赘述了

E(0)=n2

设Tn表示从0走到n的步数,于是我们有

n2=E(Tn)=2n2k=0(kP(Tn=k))+k=2n2+1(kP(Tn=k))
因为 2n2k=0(kP(Tn=k))0
所以 n2k=2n2+1(kP(Tn=k))
k=2n2+1((2n2)P(Tn=k))
=2n2P(Tn>2n2)

于是我们得到

P(Tn>2n2)12

也就是说我们从0开始走2*n*n步,我们有大于1/2的概率已经经过n这个点了。

ok回到我们的2-sat问题。

我们的算法是这样的,我们开始时随机给变量赋值0或者1,然后迭代足够多的次数(大于2*n*n的次数),如果某次迭代,我们找到了答案就可以返回结果了,如果我们迭代足够多的次数都没找到答案就返回无解。每次迭代,我们找一个不满足要求的子式,然后两个变量随机挑一个改变他的值。

假设我们现在的解是a,满足要求的解是a*,那么我们的解和满足要求的解,值不同的变量的个数是x,某次迭代,我们找到一个子式(xi or xj)不满足条件,因为子式不满足条件,所以xi和xj不可能同时和a*里值是相同的,如果两个值都不同,那么我们这次改动使得x=x-1,如果有一个值不同,那么我们有50%的概率使得x=x-1有50%的概率使得x=x+1,所以,答案变好的概率要大于50%,所以迭代2*n*n次能得到解的概率就会小于1/2。

很有趣的算法,并且我们用这个算法,可以AC掉poj 3648这道题!看代码

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <ctime>
  5. const  int maxn = 10010;
  6. int n, m, a, b;
  7. char c1, c2;
  8. int ans [maxn ], record [maxn ] [ 2 ];
  9. int get ( int x ) {
  10. if (x<n )
  11. return ans [x ];
  12. return  !ans [x -n ];
  13. }
  14. int main ( ) {
  15. //srand(time(NULL));这里如果调用time,poj会报 runtime error的错误
  16. srand ( 7 );
  17. while ( 1 ) {
  18. scanf ( "%d%d"&n,  &m );
  19. memset (ans,  0sizeof ans );
  20. if ( !n &&!m )
  21. break;
  22. for ( int i = 0; i<m;  ++i ) {
  23. scanf ( "%d%c%d%c"&a,  &c1,  &b,  &c2 );
  24. if (c1 == 'w' )
  25. += n;
  26. if (c2 == 'w' )
  27. += n;
  28. record [i ] [ 0 ]  = a;
  29. record [i ] [ 1 ]  = b;
  30. }
  31. int mark  =  0;
  32. for ( int i = 0; i< 5 *n *n;  ++i ) {
  33. mark  =  1;
  34. for ( int j = 0; j<m;  ++j )
  35. if ( (record [j ] [ 0 ] %n !=record [j ] [ 1 ] %n ) &&! (get (record [j ] [ 0 ] )||get (record [j ] [ 1 ] ) ) ) {
  36. int tmp  = rand ( ) % 2;
  37. if (record [j ] [ 0 ] %n == 0 )
  38. tmp  =  1;
  39. if (record [j ] [ 1 ] %n == 0 )
  40. tmp  =  0;
  41. ans [record [j ] [tmp ] %n ]  =  1 -ans [record [j ] [tmp ] %n ];
  42. mark  =  0;
  43. break;
  44. }
  45. if (mark )
  46. break;
  47. }
  48. if ( !mark ) {
  49. printf ( "bad luck\n" );
  50. continue;
  51. }
  52. for ( int i = 1; i<n;  ++i ) {
  53. if (ans [i ] )
  54. printf ( "%dh", i );
  55. else
  56. printf ( "%dw", i );
  57. if (i<n -1 )
  58. printf ( " " );
  59. else
  60. printf ( "\n" );
  61. }
  62. }
  63. return  0;
  64. }

记得之前gcj曾经有道题目需要用到生日悖论来解决,感觉和这个随机算法都是很有趣的算法阿。

hdu3062 Party(2-SAT入门)

分类: 2-SAT 图论 44人阅读 评论(0) 收藏 举报
2-SAT 图论

Party

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3149 Accepted Submission(s): 991


Problem Description
有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席?

Input
n: 表示有n对夫妻被邀请 (n<= 1000)
m: 表示有m 对矛盾关系 ( m < (n - 1) * (n -1))

在接下来的m行中,每行会有4个数字,分别是 A1,A2,C1,C2
A1,A2分别表示是夫妻的编号
C1,C2 表示是妻子还是丈夫 ,0表示妻子 ,1是丈夫
夫妻编号从 0 到 n -1

Output
如果存在一种情况 则输出YES
否则输出 NO

Sample Input
      
2 1 0 1 1 1

Sample Output
      
YES

Source
2009 Multi-University Training Contest 16 - Host by NIT

题目大意:中文题,不解释。

题目分析:2-sat入门题。

2-SAT就是2判定性问题,是一种特殊的逻辑判定问题。

求解过程:

1.构图
2.求图的极大强连通子图
3.把每个子图收缩成单个节点,根据原图关系构造一个有向无环图
4.判断是否有解,无解则输出(退出)
5.对新图进行拓扑排序
6.自底向上进行选择、删除
7.输出

这题只需要判断是否有解,强连通用Gabow算法。

详情请见代码:

[cpp] view plain copy print ?
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 2005;
  6. const int M = 2000000;
  7. int head[N];
  8. struct edge
  9. {
  10. int to,next;
  11. }g[M];
  12. bool flag;
  13. int stack1[N];
  14. int stack2[N];
  15. int vis[N];
  16. int scc[N];
  17. int n,m;
  18. void build(int s,int t,int num)
  19. {
  20. g[num].to = t;
  21. g[num].next = head[s];
  22. head[s] = num;
  23. }
  24. void dfs(int cur,int &sig,int &num)
  25. {
  26. if(!flag)
  27. return;
  28. vis[cur] = ++sig;
  29. stack1[++stack1[0]] = cur;
  30. stack2[++stack2[0]] = cur;
  31. for(int i = head[cur];i != -1;i = g[i].next)
  32. {
  33. if(!vis[g[i].to])
  34. dfs(g[i].to,sig,num);
  35. else
  36. {
  37. if(scc[g[i].to] == 0)
  38. {
  39. while(vis[stack2[stack2[0]]] > vis[g[i].to])
  40. stack2[0] --;
  41. }
  42. }
  43. }
  44. if(stack2[stack2[0]] == cur)
  45. {
  46. ++ num;
  47. stack2[0] --;
  48. do
  49. {
  50. scc[stack1[stack1[0]]] = num;
  51. int tmp = stack1[stack1[0]];
  52. if(tmp > n)
  53. {
  54. if(scc[tmp - n] && scc[tmp - n] == num)
  55. {
  56. flag = false;
  57. return;
  58. }
  59. }
  60. else
  61. {
  62. if(scc[tmp + n] && scc[tmp + n] == num)
  63. {
  64. flag = false;
  65. return;
  66. }
  67. }
  68. }while(stack1[stack1[0] --] != cur);
  69. }
  70. }
  71. void Gabow()
  72. {
  73. int i,sig,num;
  74. memset(vis,0,sizeof(vis));
  75. memset(scc,0,sizeof(scc));
  76. stack1[0] = stack2[0] = sig = num = 0;
  77. for(i = 1;i <= n + n && flag;i ++)
  78. if(!vis[i])
  79. dfs(i,sig,num);
  80. }
  81. int nextint()
  82. {
  83. char c;
  84. int ret;
  85. while((c = getchar()) > '9' || c < '0')
  86. ;
  87. ret = c - '0';
  88. while((c = getchar()) >= '0' && c <= '9')
  89. ret = ret * 10 + c - '0';
  90. return ret;
  91. }
  92. int main()
  93. {
  94. int i,j,a,b,c,d;
  95. while(scanf("%d",&n) != EOF)
  96. {
  97. //scanf("%d",&m);
  98. m = nextint();
  99. memset(head,-1,sizeof(head));
  100. for(i = 1;i <= m + m;i += 2)//每对矛盾建两条边
  101. {
  102. a = nextint();
  103. b = nextint();
  104. c = nextint();
  105. d = nextint();
  106. //scanf("%d%d%d%d",&a,&b,&c,&d);//1-n husband n + 1 - 2n wife
  107. a ++;
  108. b ++;
  109. switch(c + d)
  110. {
  111. case 0:build(a + n,b,i);build(b + n,a,i + 1);break;//a+n b+n 矛盾
  112. case 1:if(c)//a b + n矛盾
  113. {
  114. build(a,b,i);build(b + n,a + n,i + 1);
  115. }
  116. else//a + n b矛盾
  117. {
  118. build(a + n,b + n,i);build(b,a,i + 1);
  119. }break;
  120. case 2:build(a,b + n,i);build(b,a + n,i + 1);break;
  121. }
  122. }
  123. flag = true;
  124. Gabow();
  125. if(flag)
  126. printf("YES\n");
  127. else
  128. printf("NO\n");
  129. }
  130. return 0;
  131. }
  132. //93MS 808K

hdu4115 Eliminate the Conflict(3SAT->2SAT)

分类: 2-SAT 图论 63人阅读 评论(0) 收藏 举报
图论

Eliminate the Conflict

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 982 Accepted Submission(s): 410

Problem Description
Conflicts are everywhere in the world, from the young to the elderly, from families to countries. Conflicts cause quarrels, fights or even wars. How wonderful the world will be if all conflicts can be eliminated.Edward contributes his lifetime to invent a 'Conflict Resolution Terminal' and he has finally succeeded. This magic item has the ability to eliminate all the conflicts. It works like this:If any two people have conflict, they should simply put their hands into the 'Conflict Resolution Terminal' (which is simply a plastic tube). Then they play 'Rock, Paper and Scissors' in it. After they have decided what they will play, the tube should be opened and no one will have the chance to change. Finally, the winner have the right to rule and the loser should obey it. Conflict Eliminated!But the game is not that fair, because people may be following some patterns when they play, and if the pattern is founded by others, the others will win definitely.Alice and Bob always have conflicts with each other so they use the 'Conflict Resolution Terminal' a lot. Sadly for Bob, Alice found his pattern and can predict how Bob plays precisely. She is very kind that doesn't want to take advantage of that. So she tells Bob about it and they come up with a new way of eliminate the conflict:They will play the 'Rock, Paper and Scissors' for N round. Bob will set up some restricts on Alice.But the restrict can only be in the form of "you must play the same (or different) on the ith and jth rounds". If Alice loses in any round or break any of the rules she loses, otherwise she wins.Will Alice have a chance to win?

Input
The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.Each test case contains several lines.The first line contains two integers N,M(1 <= N <= 10000, 1 <= M <= 10000), representing how many round they will play and how many restricts are there for Alice.The next line contains N integers B 1,B 2, ...,B N, where B i represents what item Bob will play in the i th round. 1 represents Rock, 2 represents Paper, 3 represents Scissors.The following M lines each contains three integers A,B,K(1 <= A,B <= N,K = 0 or 1) represent a restrict for Alice. If K equals 0, Alice must play the same on A th and B th round. If K equals 1, she must play different items on Ath and Bthround.

Output
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is "yes" or "no" represents whether Alice has a chance to win.

Sample Input
       
2 3 3 1 1 1 1 2 1 1 3 1 2 3 1 5 5 1 2 3 2 1 1 2 1 1 3 1 1 4 1 1 5 1 2 3 0

Sample Output
       
Case #1: no Case #2: yes
Hint
'Rock, Paper and Scissors' is a game which played by two person. They should play Rock, Paper or Scissors by their hands at the same time. Rock defeats scissors, scissors defeats paper and paper defeats rock. If two people play the same item, the game is tied..

Source
2011 Asia ChengDu Regional Contest

题目大意:ACM两位神牛Alice和Bob又来玩游戏了,这次他们玩石头剪刀布。规定石头、布、剪刀分别用1、2、3表示。他们准备玩n局,现在Alice已知Bob的n局的出法,但是为了公平,对于Alice,Bob给了m个限制,每个限制3个参数:a b k。k=0或1。当k = 0的时候,表示第a局和第j局Alice必须出相同的手势,k= 1表示Alice在第a局和第j局必须出不同的手势。如果n轮比完,Alice一局没输的话,Alice赢,否则Bob赢。求Alice是否有赢的可能。

题目分析:因为每一轮有3种手势,乍一看是3-sat问题。但因为对于Alice来说,一局也不能输,所以只要n局保持不败就可以了,所以对于Alice来说,每一局其实只有2种情况,于是利用这个条件可以将此3-sat问题转化为2-sat问题。

先来看一张表:

Bob Alice

平 赢

1 1 2

2 2 3

3 3 1

一共就这6种情况。可以看出,无论Bob第a局和第b局出什么,Alice要保持不败,至少有一种手势可以在第a局和第b局同时做。所以我们先根据Bob第i局的手势,找出Alice第i局保持不败的2种手势,然后开始建图。

如果第a局和第b局Alice的手势要不同,那么矛盾的情况是Alice第a局和第b局手势相同,那么枚举这4种情况,找到矛盾的点对,建边,如果ab矛盾,建a->b',b->a'。

如果第a局和第b局Alice的手势要相同,那么矛盾的情况是Alice第a局和第b局手势不同,根据分析可知,无论第a局和第b局Bob出什么手势,Alice在这两局保持不败的策略中至少有一对是相同的,先考虑2对都相同的,即Bob在第a局和第b局手势相同,那么直接建边a->b,b->a,a + n->b + n,b + n->a + n(假设ab同,a+n b+n同),一共4条边。如果没有2对相同,那么至少一对相同,依次枚举,找到那对相同的,只有这对相同的合理,其他的都不合理,那么仿照经典的And和Or操作中的建图,假设ab相同,那么只有ab是合法的,所以直接建a+n->a,b+n->b。

详情请见代码:

[cpp] view plain copy print ?
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. const int N = 10001;
  6. const int M = 10001;
  7. struct edge
  8. {
  9. int to,next;
  10. }g[M<<1];
  11. int head[N<<1];
  12. int scc[N<<1];
  13. int vis[N<<1];
  14. int stack1[N<<1];
  15. int stack2[N<<1];
  16. int n,m,num;
  17. int lcm[N][2];
  18. bool flag;
  19. void init()
  20. {
  21. memset(head,-1,sizeof(head));
  22. memset(vis,0,sizeof(vis));
  23. memset(scc,0,sizeof(scc));
  24. stack1[0] = stack2[0] = num = 0;
  25. flag = true;
  26. }
  27. void build(int s,int e)
  28. {
  29. g[num].to = e;
  30. g[num].next = head[s];
  31. head[s] = num ++;
  32. }
  33. void dfs(int cur,int &sig,int &cnt)
  34. {
  35. if(!flag)
  36. return;
  37. vis[cur] = ++sig;
  38. stack1[++stack1[0]] = cur;
  39. stack2[++stack2[0]] = cur;
  40. for(int i = head[cur];~i;i = g[i].next)
  41. {
  42. if(!vis[g[i].to])
  43. dfs(g[i].to,sig,cnt);
  44. else
  45. {
  46. if(!scc[g[i].to])
  47. {
  48. while(vis[stack2[stack2[0]]] > vis[g[i].to])
  49. stack2[0] --;
  50. }
  51. }
  52. }
  53. if(stack2[stack2[0]] == cur)
  54. {
  55. stack2[0] --;
  56. cnt ++;
  57. do
  58. {
  59. scc[stack1[stack1[0]]] = cnt;
  60. int tmp = stack1[stack1[0]];
  61. if((tmp > n && scc[tmp - n] == cnt) || (tmp <= n && scc[tmp + n] == cnt))
  62. {
  63. flag = false;
  64. return;
  65. }
  66. }while(stack1[stack1[0] --] != cur);
  67. }
  68. }
  69. void Gabow()
  70. {
  71. int i,sig,cnt;
  72. sig = cnt = 0;
  73. for(i = 1;i <= n + n && flag;i ++)
  74. if(!vis[i])
  75. dfs(i,sig,cnt);
  76. }
  77. int nextint()
  78. {
  79. char c;
  80. int ret;
  81. while((c = getchar()) > '9' || c < '0')
  82. ;
  83. ret = c - '0';
  84. while((c = getchar()) >= '0' && c <= '9')
  85. ret = ret * 10 + c - '0';
  86. return ret;
  87. }
  88. int main()
  89. {
  90. int i,j,T,t,a,b;
  91. scanf("%d",&T);
  92. int cas = 0;
  93. while(T --)
  94. {
  95. scanf("%d%d",&n,&m);
  96. for(i = 1;i <= n;i ++)
  97. {
  98. scanf("%d",&t);
  99. lcm[i][0] = t;//tie
  100. lcm[i][1] = t + 1;//win
  101. if(lcm[i][1] > 3)
  102. lcm[i][1] = 1;
  103. if(lcm[i][0] > lcm[i][1])
  104. lcm[i][0] ^= lcm[i][1] ^= lcm[i][0] ^= lcm[i][1];
  105. }
  106. init();
  107. while(m --)
  108. {
  109. scanf("%d%d%d",&a,&b,&t);
  110. if(t)//different
  111. {//建图小心 找矛盾
  112. if(lcm[a][0] == lcm[b][0])
  113. {
  114. build(a,b + n);
  115. build(b,a + n);
  116. }
  117. if(lcm[a][0] == lcm[b][1])
  118. {
  119. build(a,b);
  120. build(b + n,a + n);
  121. }
  122. if(lcm[a][1] == lcm[b][0])
  123. {
  124. build(a + n,b + n);
  125. build(b,a);
  126. }
  127. if(lcm[a][1] == lcm[b][1])
  128. {
  129. build(a + n,b);
  130. build(b + n,a);
  131. }
  132. }
  133. else//same
  134. {
  135. if(lcm[a][0] == lcm[b][0] && lcm[a][1] == lcm[b][1])
  136. {
  137. build(a,b);
  138. build(b,a);
  139. build(a + n,b + n);
  140. build(b + n,a + n);
  141. }
  142. else
  143. {//必有一对相同的,只能选这一对
  144. if(lcm[a][0] == lcm[b][0])
  145. {
  146. build(a + n,a);
  147. build(b + n,b);
  148. }
  149. if(lcm[a][0] == lcm[b][1])
  150. {
  151. build(a + n,a);
  152. build(b,b + n);
  153. }
  154. if(lcm[a][1] == lcm[b][0])
  155. {
  156. build(a,a + n);
  157. build(b + n,b);
  158. }
  159. if(lcm[a][1] == lcm[b][1])
  160. {
  161. build(a,a + n);
  162. build(b,b + n);
  163. }
  164. }
  165. }
  166. }
  167. Gabow();
  168. printf("Case #%d: ",++cas);
  169. if(flag)
  170. printf("yes\n");
  171. else
  172. printf("no\n");
  173. }
  174. return 0;
  175. }
  176. //0MS 556K
 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/20186.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Improving Language Understanding by Generative Pre-Training 论文阅读

论文题目&#xff1a;通过生成式预训练提高语言理解能力 GPT的全称&#xff1a;Generative Pre-trained Transformer。 Generative是指GPT可以利用先前的输入文本来生成新的文本。GPT的生成过程是基于统计的&#xff0c;它可以预测输入序列的下一个单词或字符&#xff0c;从而生…

论文阅读——Recognizing Emotion Cause in Conversations

文章目录 摘要引言相关工作任务定义构造RECCON数据集情绪原因的类型实验任务1&#xff1a;Causal Span Extraction模型 任务2&#xff1a;Causal Emotion Entailment模型 面临的挑战 摘要 识别文本中情绪背后的原因是NLP中一个未被探索的研究领域。这个领域的发展具有着改善情…

论文阅读:Question Answering Over Temporal Knowledge Graphs

论文阅读&#xff1a;Question Answering Over Temporal Knowledge Graphs 我们首先在我们的新数据集上应用大型预训练的基于 LM 的 QA 方法。 然后&#xff0c;我们将时间和非时间的 KG 嵌入注入到这些 LM 中&#xff0c;并观察到性能的显着提高。 我们还提出了一种新方法 CR…

学术论文写作以及discussions/results与conclusion的区别

经验帖 | 如何写SCI论文&#xff1f; Result、Discussion和Conclusion区别解析 如何写学术论文 一篇论文只能有一个主题&#xff0c;不能出现过多的研究问题&#xff0c;这样只会让文章读起来很乱。就像大牛经常讲的&#xff0c;“one paper, one story”&#xff0c;一篇论文…

微软杀疯了!几行代码创建私人定制ChatGPT,AI办公软件帝国来了

【导读】微软又用ChatGPT出逆天操作了&#xff01;Power Virtual Agents和AI Builder推出了由Azure OpenAI服务支持的下一代AI功能。低代码技术&#xff0c;在彻底改变传统的开发格局。 微软真是逆天了。眼看&#xff0c;它就要用ChatGPT建起一个世最强办公软件帝国了&#xf…

ChatGPT 使用 拓展资料:2023年6月 吴恩达大咖Deeplearning.ai最新课程

ChatGPT 使用 拓展资料:2023年6月 吴恩达大咖Deeplearning.ai最新课程 Deeplearning.ai刚刚发布几个新的课程https://www.deeplearning.ai/short-courses/?utm_campaign=May%20Short%20Course%20Launch&utm_content=250952287&utm_medium=social&utm_source=link…

使用Python把树莓派改造成一个语音助手

CSDN广告邮件太多了&#xff0c;邮箱已经屏蔽了CSDN&#xff0c;留言请转SegmentFault&#xff1a;https://segmentfault.com/a/1190000014000349 语音助手已经不是什么新事物了。就在两三年前&#xff0c;语音助手的使用体验还不是那么好&#xff0c;尝尝鲜后也就没用过了。但…

AI对话-Free Chat免费无限制

目录 前言 使用方法 提问 推荐线路 前言 chat.4 和 chat.5 线路的响应改成通过在 Netlify 的部署来响应了。Netlify 不像 Vercel 那样还限制 Edge Function 的调用次数,很适合部署本项目。现在这两个线路的成本最低了,最优先推荐大家使用。 使用方法 提问 比如我问他:…

掌握唯米系统ChatGPT批量生成文章的操作技巧

以下是重写后的操作步骤&#xff1a; 1. 购买会员并添加个人的ChatGPT密钥&#xff1a; 首先&#xff0c;您需要购买唯米系统的会员&#xff0c;并获得访问ChatGPT的权限。随后&#xff0c;您可以将个人的ChatGPT密钥添加到系统中&#xff0c;以便使用该功能进行自然语言生成和…

ChatGPT批量生成文章软件:创意无限,智能驱动文章

随着人工智能技术的不断发展&#xff0c;ChatGPT批量生成文章软件成为了当今互联网世界中备受瞩目的创新之一。作为一种基于大规模预训练语言模型的自然语言处理工具&#xff0c;ChatGPT能够以人类般的方式与用户进行对话&#xff0c;并且能够生成高质量的文章。这一技术的出现…

ChatGPT3.5 AI智能高质量原创文章批量生成器 API方式多个key多线程写文章

1、ChatGPT3.5是一种基于自然语言处理技术的模型&#xff0c;可以模拟人类写作和思考的过程&#xff0c;生成通顺、有逻辑、富有创造性的文章。 2、使用ChatGPT3.5&#xff0c;您可以快速轻松地生成各种类型的文章&#xff0c;无论是新闻报道、产品说明、营销宣传、科技评论&a…

技术科普与解读:ChatGPT 大模型硬核解读!(一)家族历史从GPT-1到ChatGPT

多模态&#xff0c;指的是融合文本、图像、视频或音频等多种模态作为输入或输出。 GPT-4是严格意义上的多模态模型&#xff0c;可以支持图像和文字两类信息的同时输入&#xff0c;输出为文本。从学术界的分析来看&#xff0c;无论是知识/能力获取还是与现实物理世界的交互&…

【宏观经济学】chatGPT会让我们失业吗?

文章链接&#xff1a;chatGPT会让我们失业吗&#xff1f;

Transformer模型详解

2013年----word Embedding 2017年----Transformer 2018年----ELMo、Transformer-decoder、GPT-1、BERT 2019年----Transformer-XL、XLNet、GPT-2 2020年----GPT-3 Transformer 谷歌提出的Transformer模型&#xff0c;用全Attention的结构代替的LSTM&#xff0c;在翻译上取得了更…

阐述说明NLP发展历史,以及 NLP与chatgpt的关系

自然语言处理&#xff08;Natural Language Processing&#xff0c;NLP&#xff09;是人工智能&#xff08;AI&#xff09;领域的一个重要分支&#xff0c;关注计算机与人类&#xff08;自然&#xff09;语言之间的交互。NLP的目标是使计算机能够理解、生成和解释自然语言&…

【GPT】你需要了解的 ChatGPT的技术原理- Transformer架构及NLP技术演进

目录 概述 The Concept of Transformers and Training A Transformers ModelTransformers 的概念和训练 Transformers 模型

思科模拟器之端口聚合技术

端口聚合也叫做以太通道&#xff08;ethernet channel&#xff09;&#xff0c;主要用于交换机之间连接。由于两个交换机之间有多条冗余链路的时候&#xff0c;STP会将其中的几条链路关闭&#xff0c;只保留一条&#xff0c;这样可以避免二层的环路产生。 工作原理&#xff1a…

如何在群晖NAS上安装cpolar内网穿透

系列文章 做内网穿透外网远程访问群晖NAS 1-2做内网穿透外网远程访问群晖NAS 2-2如何在群晖NAS上安装cpolar内网穿透配置群晖NAS中的cpolar开机自启动 1-2配置群晖NAS中的cpolar开机自启动 2-2为公网远程访问群晖NAS配置固定域名 1-2为公网远程访问群晖NAS配置固定域名 2-2 上…

如何使用cpolar内网穿透群晖NAS套件

系列文章 如何安装cpolar内网穿透群晖NAS套件如何使用cpolar内网穿透群晖NAS套件 上一篇&#xff1a; 如何安装cpolar内网穿透群晖NAS套件 在上一篇介绍里&#xff0c;我们在群晖系统中成功安装了图形化界面的cpolar&#xff0c;由于cpolar从命令行界面转入图形化界面&#xf…

QNAP威联通NAS搭建SFTP服务,并内网穿透实现公网远程访问

文章目录 前言1. 威联通NAS启用SFTP2. 测试局域网访问3. 内网穿透3.1 威联通安装cpolar内网穿透3.2 创建隧道3.3 测试公网远程访问 4. 配置固定公网TCP端口地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址4.3 测试使用固定TCP端口地址远程连接威联通SFTP 转载自远程内…