spoj 2321 Segments

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

二分 + 差分约束

题意:给出n条水平的线段,给出线段的两个端点(但是线段不包括它们的端点),它们有高度。然后你要画一些竖直的直线,穿过这些水平直线。每次水平直线都至少要被穿过一次。但是有些水平直线可能会被多条竖直直线穿过,每个水平直线被穿过的次数是ci,你的任务是计算出,最大值的最小值,即令到max{ ci } 这个最小

这个问题要转化为差分约束来做。

先做一个预处理,因为线段不能包含端点,假设3条直线(1,3)(3,4)(-10,10),是不是只需要一条垂直直线就行了呢?从3这个点穿下去,3条直线都能穿到了是吧?不是的,因为3这个端点不属于第1,2条直线,从3穿下去,第1,2条直线不会被穿到

处理端点的方法是 a = a 2 + 1 , b = 2 b(或a = 2 a, b = 2 b - 1,一样的)

另外端点的范围没有过出,要做离散化,这里直接用map来保存映射结果

然后重点是怎么转化为差分约束

设一个值c[i],表示从最左端开始(可以理解为负无穷或线段端点中的最左那个),到i这个坐标已经有了多少条直线

那么对于所有水平线段的两个经过预处理的端点ai,bi而言,c[bi] - c[ai] >= 1,即任何一条直线都至少被一条直线穿过

另外对于直线中的两点之间也好,还是两个直线间隔的那个部分也好,都满足c[y] - c[x] >= 0,即要么有直线要么没有直线穿过,不可能出现负数

最后,我们可以假设一条水平直线被最多的竖直直线穿过,条数是m,那么对于所有水平直线都满足c[bi] = c[ai] <= m

这一系列的不等式,组成了一个差分约束系统,对这个差分约束系统求解,如果所有等式都可以满足,那么m就是一个可行解

现在我们就是不知道m的值,但是我们知道这个值的范围,为什么呢?m>=1是显然的,至少一条。m<=n-1,这是因为,极端情况下,一条水平直线非常长,可以涵盖其余所有水平直线,而刚好其余水平直线都是分隔开的,那么每条水平直线都需要一条竖直直线穿过,一共n-1条,这n-1条线都穿过了最长的那条水平直线,所以一条水平直线,最多被n-1条竖直直线穿过

这时候可以二分答案了,答案一定为[1,n-1],没枚举出一个答案m,就带入到那些不等式中, 对差分约束系统求解,如果成立,是一个可行解,就可以试着缩小m的值,所以向下二分。如果差分约束系统不成立,说明m不是一个可行解,将m增加,向上二分

差分约束就是转化为最短路问题求解,有负环,系统无解,无负环,系统有解

写了3个代码来测速度

Bellman-Ford判负环 0.08左右

spfa_bfs 2.0左右

spfa_dfs 0.05左右最快,排在18名

Bellman-Ford

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define N 410
#define MAX 5000
#define INF 0x3f3f3f3f
#define ll long long
#define cl memset
#define pb push_back

int n,tot,len;
ll x[N],y[N],list[2*N];
int d[2*N];
struct edge{
int u,v,w;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[MAX];
map<ll,int>Hash;

void init(){ //将端点离散化:排序,去重,映射
sort(list,list+len); //排序
int index = 1; //去重
for(int i = 1; i < len; i++)
if(list[i] != list[i-1])
list[index++] = list[i];
len = index; //去重完毕
Hash.clear();
for(int i = 0; i < len; i++)
Hash[list[i]] = i; //将list[i]映射到i
}

void build(){ //构图但没有全部构完
tot = 0;
for(int i = 0; i < n; i++){
int a = Hash[x[i]] , b = Hash[y[i]];
e[tot++] = edge(a,b,INF);
}
for(int i = 1; i < len; i++) //两间的直线数 >= 0
e[tot++] = edge(i,i-1,0);
for(int i = 0; i < n; i++){ //c[b] - c[a] >= 1
int a = Hash[x[i]] , b = Hash[y[i]];
e[tot++] = edge(b,a,-1);
}
}

bool check(int p){
for(int i = 0; i < len; i++)
d[i] = (i == 0 ? 0 : INF);
bool ok = true;
for(int i = 0; i < len ; i++){ //Bellman-Ford判负环
ok = true;
for(int k = 0; k < tot; k++){
int u = e[k].u , v = e[k].v , w = e[k].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w; ok = false;
}
}
if(ok) return ok;
}
return ok; //true是无负环,false是有负环
}

void binary(){ //二分答案
int low = 1 , high = n-1 , ans = 1;
while(low <= high){
int mid = (low + high) >> 1;

for(int i = 0; i < n; i++) e[i].w = mid; //每次改变前n条边的权
if(check(mid)){
ans = mid; high = mid - 1;
}
else low = mid + 1;
}
printf("%d\n",ans);
}

int main(){
while(scanf("%d",&n)!=EOF){
ll h;
len = 0;
for(int i = 0; i < n ; i++){
cin >> x[i] >> y[i] >> h;
x[i] = (x[i]<<1) + 1 ; y[i] <<= 1;
list[len++] = x[i]; list[len++] = y[i];
}
init();
build();
binary();
}
return 0;
}

spfa(dfs和bfs代码都写在里面的,可以直接调用)

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define N 410
#define MAX 5010
#define INF 0x3f3f3f3f
#define ll long long
#define cl memset
#define pb push_back

bool vis[2*N];
int n,tot,len,head[2*N],d[2*N];
struct edge{
int u,v,w,next;
}e[MAX];
ll x[N],y[N],list[2*N];
map<ll,int>Hash;
queue<int>que;

void init(){
sort(list,list+len);
int index = 1;
for(int i = 1; i < len; i++)
if(list[i] != list[i-1])
list[index++] = list[i];
len = index;
Hash.clear();
for(int i = 0; i < len; i++)
Hash[list[i]] = i;
}

inline void add(int u,int v,int w){
e[tot].u = u; e[tot].v = v; e[tot].w = w;
e[tot].next = head[u]; head[u] = tot++;
}

void build(){
tot = 0;
cl(head,-1,sizeof(head));
for(int i = 0; i < n; i++){ //这n条边添加了,但是没有对边权赋值,因为以后二分时每次都要修改
int a = Hash[x[i]] , b = Hash[y[i]];
add(a,b,INF);
}
for(int i = 1; i < len; i++)
add(i,i-1,0);
for(int i = 0; i < n; i++){
int a = Hash[x[i]] , b = Hash[y[i]];
add(b,a,-1);
}
}

bool spfa_dfs(int u){
vis[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v , w = e[k].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
if(!vis[v]){
if(spfa_dfs(v)) return true;
}
else return true;
}
}
vis[u] = false;
return false;
}

bool spfa_bfs(){
int c[2*N];
while(!que.empty()) que.pop();
cl(c,0,sizeof(c));
que.push(0); vis[0] = true;
while(!que.empty()){
int u = que.front();
que.pop(); vis[u] = false;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v , w = e[k].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
if(!vis[v]){
que.push(v); vis[v] = true; c[v]++;
if(c[v] == len) return false;
}
}
}
}
return true;
}

bool check(){
cl(vis,false,sizeof(vis));
for(int i = 0; i < len; i++)
d[i] = (i == 0 ? 0 : INF);
return (!spfa_dfs(0));
// return spfa_bfs();
}

void binary(){
int low = 1 , high = n-1 , ans = 1;
while(low <= high){
int mid = (low + high) >> 1;

for(int i = 0; i < n; i++) e[i].w = mid;

if(check()){
ans = mid; high = mid - 1;
}
else low = mid + 1;
}
cout << ans << endl;
}

int main(){
while(cin >> n){
len = 0;
for(int i = 0; i < n; i++){
ll h;
cin >> x[i] >> y[i] >> h;
x[i] = (x[i]*2) + 1; y[i] *= 2;
list[len++] = x[i]; list[len++] = y[i];
}
init();
build();
binary();
}
return 0;
}