本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分 + 2-sat判定
题意:略
断断续续学了一下2-sat,经过这题算是对2-sat的理解更深一点。2-sat整个题就是在于怎么构图,构好图整个题就很裸露了。 2-SAT建图原则,建边的都是建立必要关系,是由矛盾关系推导过来的
一个矛盾关系,必然对应一个必然关系,但是注意还有一些关系,并不是必然的,这些不能建边
说回这题,其实a,b数组只是起到了一个index的作用,即指向了x数组的位置,而c数组则是反映一种矛盾关系。2-sat模型中,都是有n对物品,即2n个物品,它们存在限制关系,这里的n对物品其实就是x数组。
注意题中并没有给出x数组,其实题意就是说,根据a和b和c提供的这些限制关系,能不能构出一个x数组,使之满足前面的m个限制关系。当取出越多的abc时,即添加的限制关系越多,想构建出一个x数组就更难。
我们直接说解法
取出了a[i],b[i],c[i],其实就是取出了一对限制关系,来看看这些限制关系怎么表达的;a[i],b[i],c[i]下面都用a,b,c表示
当c = 0 , x[a] + x[b] != c才能到下一层,也就是要满足这个关系才能到下一层,这个关系是什么?就是第a个元素+第b个元素不能同时等于0,也就是第a个元素和第b个元素不能都不选,它们的等价就是,a和b一定要选一个,注意这是个必要关系,再换一话说就是,当a不选b一定选,b不选a一定选。这里注意了,a选b也选是个什么关系,注意,这个关系,是合法的,但却不是必然关系,因为a和b不能都不选,并不等价于a和b都选。
所以只能建边 ~a->b , ~b->a
当c = 1 , x[a] + x[b] != c才能到下一层,也就是要满足这个关系才能到下一层,这个关系就是,第a个和第b个不能不同,a和b一旦不同,即01,10的时候,这个就不能到下一层了。那么a和b不能不同,文字描述就是a和b不能只选一个,对应的必然关系是什么?那就是a和b一定要同啊!也就是第a个和第b个要么同时选要么同时不选,也就是是a是0的时候,b一定要是0,a是1的时候b一定要是1,同样的,b是0的时候a一定要是0,b是1的时候a一定要是1
所以只能建边 a->b , a->b , b->a , b->a
当c = 2 , x[a] + x[b] != c才能到下一层,也就是第a个和第b个不能同时选不能同时为1,这个对应的必然关系是什么,就是选a不选b,选b不选a,那么可不可以不选a也不选b,是可以的,但是这个并不是一个必然关系,并不是一个要满足的。同样的,那么不选a了,是不是一定要选b,也不是的!这也不是必然关系!因为不选a,可以选b也可以不选b!
所以建边 a->b , b->a
构好图,2-sat模板上去,求个强连通,判断一下是否存在可行解即可
另外答案不确定,是二分出来的,答案一定在[0,m],所以二分它。最前面说了,其实一组abc就是一组关系,当添加的关系越多时,想构建出x数组是越难的,所以枚举出一个答案ans时,如果存在可行解解,那么就试着把ans提高,即再添加一些关系看看是否可行,向上二分。如果没有可行解,那么说明关系太多了因为构不成一个x数组,再添加更加构不成,所以只好减少关系的组数,向下二分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 #include <iostream> #include <cstdio> #include <cstring> #include <cstdio> #include <vector> using namespace std;#define N 210 #define MAX 320010 #define M 10010 #define INF 0x3f3f3f3f #define cl memset int n,m,a[M],b[M],c[M];int tot,head[2 *N];struct edge { int u,v,next; }e[MAX]; int dfn[2 *N],low[2 *N],belong[2 *N],stack[2 *N],dcnt,bcnt,top;bool ins[2 *N];inline void add (int u,int v) { e[tot].u = u; e[tot].v = v; e[tot].next = head[u]; head[u] = tot++; } void build (int num) { tot = 0 ; cl (head,-1 ,sizeof (head)); for (int i = 0 ; i < num; i++){ int u = a[i],v = b[i]; if (c[i] == 0 ){ add (u<<1 ,v<<1 |1 ); add (v<<1 ,u<<1 |1 ); } else if (c[i] == 1 ){ add (u<<1 ,v<<1 ); add (u<<1 |1 ,v<<1 |1 ); add (v<<1 ,u<<1 ); add (v<<1 |1 ,u<<1 |1 ); } else { add (u<<1 |1 ,v<<1 ); add (v<<1 |1 ,u<<1 ); } } } void tarjan (int u) { dfn[u] = low[u] = ++dcnt; stack[++top] = u; ins[u] = true ; for (int k = head[u]; k != -1 ; k = e[k].next){ int v = e[k].v; if (!dfn[v]){ tarjan (v); low[u] = min (low[u],low[v]); } else if (ins[v]) low[u] = min (low[u],dfn[v]); } if (dfn[u] == low[u]){ ++bcnt; while (true ){ int x = stack[top--]; ins[x] = false ; belong[x] = bcnt; if (x == u) break ; } } } bool check () { dcnt = bcnt = top = 0 ; cl (dfn,0 ,sizeof (dfn)); cl (ins,false ,sizeof (ins)); for (int i = 0 ; i < 2 *n; i++) if (!dfn[i]) tarjan (i); for (int i = 0 ; i < n; i++) if (belong[i<<1 ] == belong[i<<1 |1 ]) return false ; return true ; } int main () { int cas; scanf ("%d" ,&cas); while (cas--){ scanf ("%d%d" ,&n,&m); for (int i = 0 ; i < m; i++) scanf ("%d%d%d" ,&a[i],&b[i],&c[i]); int low = 0 , high = m , ans = 0 ; while (low <= high){ int mid = (low + high) >> 1 ; build (mid); if (check ()){ ans = mid; low = mid + 1 ; } else high = mid - 1 ; } printf ("%d\n" ,ans); } return 0 ; }