hdu 3715 Go Deeper

本文从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
/*
2-SAT建图原则,建的都是必要关系,是由矛盾关系推导过来的
一个矛盾关系,必然对应一个必然关系,但是注意还有一些关系,并不是必然的,这些不能建
*/
#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;
}