G-rated

What are you waiting for?

0%

poj 2749 Building roads

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

二分 + 2-sat判定

题意：有两个中转站s1,s2，另外n个农场，要将这些农场直接连接在这2个中转站上，但是只能连其中一个。但是n个农场中，某2个农场之间存在hate关系，他们不能同时连在同一个中转站，某2个农场存在friend关系，他们必须连在同一个农场里。另外s1,s2和每个农场都有坐标，任意两个农场之间有曼哈顿记录，是这样计算的

  1. 如果a和b农场都连在s1上，距离是dis(a,s1) + dis(b,s1)
  2. 如果a和b农场都连在s2上，距离是dis(a,s2) + dis(b,s2)
  3. 如果a在s1，b在s2，距离是dis(a,s1) + dis(s1,s2) + dis(b,s2)

注意这里的dis都是两点间的曼哈顿距离

你的任务是计算出连接后两点曼哈顿距离最大值的最小值

最大值最小，二分，点的坐标范围给出了，所以曼哈顿距离的范围也是知道的，以此二分

二分答案后用2-sat检验

对于一个农场，用a表示连在s1，~a连在s2

  1. 对于hate关系

    u和v不能连在同一个站，所以得到必然关系

    u->v , ~u->v , v->u , ~v->u

  2. 对于friend

    2点必连在一起，也得到必然关系

    u->v , u->v , v->u , ~v->u

  3. 每次二分出一个最远曼哈顿距离s，那么图中任意两点的曼哈顿距离都应该 >= s，如果出现矛盾，那么就以矛盾对应的必然关系加边

    1. u和v都连s1 dis(u,s1) + dis(v,s1) > s ， 出现矛盾，必然关系是两者不能都连s1 u->v , v->u
    2. u和v都连s2 dis(u,s2) + dis(v,s2) > s , 出现矛盾，必然关系是两者不能都连s2 ~u->v , ~v->u
    3. u连s1，v连s2 dis(u,s1) + dis(s1,s2) + dis(v,s2) > s ,出现矛盾，必然关系是，u连s1时v不能连s2只能连s1，v连s2时u不能连s1只能连s2 u->v , u->v
    4. u连s2，v连s1
     dis(u,s2) + dis(s1,s2) + dis(v,s1) > s , 出现矛盾，必然关系是，u连s2时v不能连s1只能连s2，v连s1时u不能连s2只能连s1

 ~u->~v , v->u

构图完毕

(注意构图简单来说分成两个部分，一部分是利用hate和friend关系来构图，这部分是不变的，令一部分，是根据当前二分出来的答案s来构的，不停变化。在代码中，每次二分出答案后，都是两部分同时重新构图，一个优化是，对于hate和friend部分的边，不要每次都重新添加，不过可以要改变构图函数的写法)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 510
#define M 1010
#define MAX 4000000
#define cl memset
#define pb push_back

vector<int>e[2*N];
int sx1,sy1,sx2,sy2;
int n,x[N],y[N];
int hn,h[M][2]; //讨厌关系
int fn,f[M][2]; //朋友关系
int dcnt,bcnt,top,dfn[2*N],low[2*N],belong[2*N],stack[2*N];
bool ins[2*N];

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

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

inline int dis_s1_s2(){
	return abs(sx1-sx2) + abs(sy1-sy2);
}

inline int dis(int u ,int k){
	if(k == 1)
		return abs(x[u]-sx1) + abs(y[u]-sy1);
	else
		return abs(x[u]-sx2) + abs(y[u]-sy2);
}

void build(int s){
	for(int i = 0; i < 2*n; i++)
		e[i].clear();
	for(int i = 0; i < hn; i++){
		int u = h[i][0] , v = h[i][1];
		add(u<<1,v<<1|1); add(u<<1|1,v<<1); 
		add(v<<1,u<<1|1); add(v<<1|1,u<<1);
	}
	for(int i = 0; i < fn; i++){
		int u = f[i][0] , v = f[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);
	}
	for(int u = 0; u < n; u++)
		for(int v = u+1; v < n; v++){
			if(dis(u,1) + dis(v,1) > s){
				add(u<<1,v<<1|1); add(v<<1,u<<1|1);
			}
			if(dis(u,2) + dis(v,2) > s){
				add(u<<1|1,v<<1); add(v<<1|1,u<<1);
			}
			if(dis(u,1) + dis_s1_s2() + dis(v,2) > s){
				add(u<<1,v<<1); add(v<<1|1,u<<1|1);
			}
			if(dis(u,2) + dis_s1_s2() + dis(v,1) > s){
				add(u<<1|1,v<<1|1); add(v<<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(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%d",&n,&hn,&fn)!=EOF){
		scanf("%d%d%d%d",&sx1,&sy1,&sx2,&sy2);
		for(int i = 0; i < n; i++)
			scanf("%d%d",&x[i],&y[i]);
		for(int i = 0; i < hn; i++){
			scanf("%d%d",&h[i][0],&h[i][1]);
			h[i][0]--; h[i][1]--;
		}
		for(int i = 0; i < fn; i++){
			scanf("%d%d",&f[i][0],&f[i][1]);
			f[i][0]--; f[i][1]--;
		}

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