uva 1146 Now or later

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

二份答案 + 2-sat判定

题意:有n个飞机,它们有早和晚降落时间,现在要使每个飞机都能下降,但是任意两个飞机不能同时降落,让你给飞机安排下落时间。另外使到任意两个飞机的降落的最短时间间隔最大。只是需要输出这个时间

最小值最大,这类问题就是二分答案了。我们枚举一个时间T,作为所有飞机降落的最短间隔,意思就是任意两个飞机的降落时间差都是大于等于这个T,如果能满足这个条件,那么这个T就是一个答案,既然这个答案满足,我们就可以试着去找一个更大的答案(因为我们是要最大值),所以就想上二分,如果这个T不满足,那么只好缩小这个T,向下二分。

至于怎么判定这个T是否合法,就要用2-sat了。我们先假定一个T成立,那么我们枚举任意两个飞机i,j,他们的早晚降落时间分别为ai,bi,aj,bj

如果abs(ai-bi) < T,也就是这两个时间间隔小于T,那么这两个时间是不能共存的,即一对矛盾关系,那么我们就可以添加边 ai->bj , bi->aj

同样的我们枚举abs(ai,bj),abs(aj,bi),abs(aj,bj),用同样的方法建图。
建好图后只需要求解这个2-sat是否存在可行解即可吗,不需要输出答案

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
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int N = 4010;
const int M = 32000010;
#define cl memset
#define pb push_back

int t[N];
int n,tot,head[N];
struct edge{
int u,v,next;
}e[M];
int dfn[N],low[N],belong[N],stack[N],dcnt,bcnt,top;
bool ins[N];
int opp[N];

inline int abs(int x){
return x > 0 ? x : -x;
}

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 T){
tot = 0;
cl(head,-1,sizeof(head));
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++){
int t1 = t[i<<1] , t2 = t[i<<1|1];
int t3 = t[j<<1] , t4 = t[j<<1|1];
if(abs(t1-t3) < T){
add(i<<1,j<<1|1); add(j<<1,i<<1|1);
}
if(abs(t1-t4) < T){
add(i<<1,j<<1); add(j<<1|1,i<<1|1);
}
if(abs(t2-t3) < T){
add(i<<1|1,j<<1|1); add(j<<1,i<<1);
}
if(abs(t2-t4) < T){
add(i<<1|1,j<<1); add(j<<1|1,i<<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;
}
}
}

void scc(){
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);
}

bool check(int T){
build(T);
scc();
for(int i = 0; i < n ; i++)
if(belong[i<<1] == belong[i<<1|1])
return false;
return true;
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 0; i < n ;i++)
scanf("%d%d",&t[i<<1],&t[i<<1|1]);
int left = 1,right = -1,res = -1;

for(int i = 0; i < n ; i++)
for(int j = i + 1; j < n; j++){
right = max(right,abs(t[i<<1]-t[j<<1|1]));
right = max(right,abs(t[j<<1]-t[i<<1|1]));
}

while(left <= right){
int mid = (left + right) >> 1;
if(check(mid)){
left = mid + 1;
res = mid;
}
else
right = mid - 1;
}
printf("%d\n",res);
}
return 0;
}