hdu 1816 Get Luffy Out *

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

二分 + 2-sat判定

题意:和poj 2723 差不多一样的题意.poj说的是是给出n对钥匙,一定保证是有2n把的,每个钥匙只出现一次。这次里面,n对钥匙里,某些钥匙出现了多次,这导致有些钥匙可以选到

例如 1 3 , 1 3,第一次用了3,那么1不见了,但是第2次可以用1,3不见了,这样1和3都能用到,这在poj那题里是不同的,poj那题1和3是不可能同时用到的。

至于poj那题怎么构图就自行搜索博客了,这里只说这题怎么构图

n对钥匙拆成2点,表示选和不选,u<<1选,u<<1|1不选。

对于一对钥匙a b,选a不选b,选b不选a

对于一个门的两个钥匙a b,不选a选b,不选b选a

构图完毕(注意n对钥匙,2n个钥匙,拆点后4n点)

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
/*
一个钥匙有选或不选,每个钥匙拆成两点
一对钥匙a,b。选a不选b,选b不选a
对于一个门的两个锁a,b,不选a必选b,不选b必选a
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 1050
#define M 2100
#define cl(ab,cd) memset((ab),(cd),sizeof((ab)))
#define pb push_back

int n,m;
vector<int>e[4*N];
int a[N],b[N],p[M],q[M];
int dfn[4*N],low[4*N],belong[4*N],stack[4*N],dcnt,bcnt,top;
bool ins[4*N];

inline void add(int u,int v){
e[u].pb(v);
}

void build(int cnt){
for(int i = 0; i < 4*n; i++)
e[i].clear();
for(int i = 0; i < n; i++){
int u = a[i],v = b[i];
add(u<<1,v<<1|1); add(v<<1,u<<1|1);
}
for(int i = 0; i <= cnt; i++){
int u = p[i],v = q[i];
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 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(low[u] == dfn[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);
//memset(dfn,0,sizeof(dfn));
//memset(ins,false,sizeof(ins));
for(int i = 0; i < 4*n; i++)
if(!dfn[i])
tarjan(i);
for(int i = 0; i < 2*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 < n; i++)
scanf("%d%d",&a[i],&b[i]);
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;
}