poj 2723 Get Luffy Out

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分 + 2-sat判定

题意:有2n把钥匙,从0到2n-1标号。但是这些钥匙,被分成了n组,每组两把钥匙,他们被捆绑在一起,选了这组组内的两把钥匙都要选;另外有m个门,每个门有两个锁,锁也是0到2n-1标号,对应的钥匙可以开对应的锁,要开一个门只需要开其中一个锁即可。当用一把钥匙开门时,跟它捆绑在一起的另一把钥匙会消失掉,但是注意,这把钥匙这次开门后,还是可以留着以后多次开门用的,它不会消失。给出n组钥匙的捆绑情况和m个门的锁的情况,问在最佳选择下,最多可以开到几个门

能开最多的门,那么就二分吧

至于而分出一个答案,用2-sat检验。我的做法和网上的题解不同。网上题解都说,对于一组钥匙a,b,它们被捆绑在一起,那么就是选的时候是一起选的,所以要加一条边。这样固然是对的。但是我利用的时候消失这个条件,钥匙给出时,一定给出2n个每个钥匙出现一次,对已一对捆绑的钥匙,它们其实只能用其中1个,想想2-sat的经典模型就是有n对物品,每对物品只能选其中之一,所以这里我们就把每对钥匙看做每对物品,但是每对钥匙的编号不是连续对应的,那么我们就可以映射一次啊

1
2
3
例如sample
0 3 1 2 4 5 映射为
0 1 2 3 4 5 这样就成了n对物品,每对物品间必然是选其一的,所以不需要对钥匙另外加边了

至于门上的锁是怎么联系起来的?一个门有a,b两个锁,你要开这个门,至少开一个锁,也就是你至少要有a,b其中一把钥匙,所以这个就是一个至少选1的关系

~a->b , ~b->a 当一个不选的时候,另一个必须选

构图完毕了

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
/*
将钥匙重新映射后,每组钥匙之间就不需要另外加边了
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1050
#define M 3010
#define cl memset
#define pb push_back

vector<int>e[2*N];
int n,m,Hash[2*N];
int a[M],b[M];
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[u].pb(v);
}

void build(int num){
for(int i = 0; i < 2*n; i++)
e[i].clear();
for(int i = 0; i <= num; i++){
int u = Hash[a[i]] , v = Hash[b[i]];
add(u^1,v); add(v^1,u);
}
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
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(){
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
for(int i = 0; i < 2*n; i++){
int x;
scanf("%d",&x);
Hash[x] = i;
}
for(int i = 0; i < m; i++)
scanf("%d%d",&a[i],&b[i]);
int low = 0,high = m-1,ans = 1;
while(low <= high){
int mid = (low + high) >> 1;
build(mid);
if(check()){
low = mid + 1; ans = mid + 1;
}
else high = mid - 1;
}
printf("%d\n",ans);
}
return 0;
}

另一种思路,一对钥匙不能同时共存,而一个门的两个锁必须要开一个。假设一对钥匙a,b,记录它们各自的对立者,opp[a] = b; opp[b] = a;在开门的时候,两个锁p,q,如果不选p必选q,不选q必选p(这样至少才能开门),那么不选p的时候还有一个关系是什么,就是必选p的对立者,p的对立者就看p在哪对钥匙里,另外那个钥匙就是对立者。那么整个关系应该是这样的,选了p的对立者opp[p],那么p不能选,p不能选,意味着q一定要选,也就是选了opp[p]一定要选q,加边opp[p] -> q

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1050
#define M 2100
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,m;
int opp[2*N],p[M],q[M];
vector<int>e[2*N];
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[u].pb(v);
}

void build(int cnt){
for(int i = 0; i < 2*n; i++)
e[i].clear();
for(int i = 0; i <= cnt; i++){
int u,v;
u = opp[p[i]]; v = q[i];
add(u,v);
u = opp[q[i]]; v = p[i];
add(u,v);
}
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
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);
cl(ins,false);
for(int i = 0; i < 2*n; i++)
if(!dfn[i])
tarjan(i);
for(int i = 0; i < 2*n; i++)
if(belong[i] == belong[opp[i]])
return false;
return true;
}


int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
for(int i = 0; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
opp[u] = v; opp[v] = u;
}
for(int i = 0; i < m; i++)
scanf("%d%d",&p[i],&q[i]);
int low = 0 , high = m - 1 , ans = 0;
while(low <= high){
int mid = (low + high) >> 1;
build(mid);
if(check()){
low = mid + 1; ans = mid + 1;
}
else high = mid - 1;
}
printf("%d\n",ans);
}
return 0;
}