G-rated

What are you waiting for?

0%

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;
}