백준13145 Masonry Bridge

작성일 | In

문제 링크

  • http://icpc.me/13145

사용 알고리즘

  • 듀얼 그래프
  • 다익스트라

풀이

최소 비용은 다익스트라로 쉽게 구할 수 있으니까 넘어가고, 최대 비용을 구하는 방법을 생각해봅시다.

주어지는 그래프가 평면 그래프이기 때문에 Dual Graph를 생각해볼 수 있습니다.

일반적인 dual graph는 위 그림처럼 바깥쪽 영역을 하나의 영역으로 간주합니다. 바깥쪽 영역을 조금 더 자세하게 표현하기 위해 4개의 정점과 6개의 간선을 추가해봅시다.

1번 정점과 N번 정점이 연결되기 전까지는 원본 그래프에서 아직 건설하지 않은 간선들만 이용해 up에서 down으로 갈 수 있습니다.
1번 정점과 N번 정점이 연결된 후에는 건설하지 않은 간선들만을 이용해 up에서 down으로 갈 수 없습니다.

마지막에 건설하는 간선이 평면 P-Q를 연결하는 간선이라면 정답은 (전체 간선의 가중치 합) - (up에서 P까지의 최단 거리) - (down에서 Q까지의 최단 거리)가 됩니다.
이것은 up에서 출발하는 다익스트라와 down에서 출발하는 다익스트라를 각각 돌려준 다음, 모든 간선에 대해 all - D1[P] - D2[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
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
const ll inf = 1e9+7;

//par : union find
//id : 모든 union 연산이 끝난 후, 각 정점의 그룹 번호
int par[303030], id[303030];
int find(int v){ return v == par[v] ? v : par[v] = find(par[v]); }
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u ^ v) par[u] = v;
}
int ccw(p a, p b, p c){
    ll res = a.x*b.y + b.x*c.y + c.x*a.y;
    res -= b.x*a.y + c.x*b.y + a.x*c.y;
    if(res > 0) return 1;
    if(res) return -1;
    return 0;
}

int n, m;
p pt[101010]; //주어지는 점들의 좌표
vector<p> g[101010]; //g[s].push_Back({e, 간선 번호})
vector<p> dual[101010]; //dual[s].push_back({e, 간선 번호})
ll w[303030], sum; //w : 간선의 가중치, sum : 모든 간선 가중치의 합
vector<int> dual_pt; //평면 번호 좌표 압축용 배열
int LU, LD, RU, RD; //더미 정점
int LUE, LDE, RUE, RDE, UE, DE; //더미 간선

//각도 정렬
p base;
bool cmp_angle(const p &_a, const p &_b){
    p a = pt[_a.x], b = pt[_b.x];
    if((a > base) != (b > base)) return a > b;
    return ccw(a, base, b) > 0;
}

//get dual graph
void getDual(){
	iota(par, par+303030, 0);
  //각도 정렬 후 점 병합
	for(int i=1; i<=n; i++){
		base = pt[i]; sort(all(g[i]), cmp_angle);
		for(int j=0; j<g[i].size(); j++){
			int k = j ? j-1 : (int)g[i].size()-1;
			int u = g[i][k].y << 1 | 1, v = g[i][j].y << 1;
			p p1 = pt[g[i][k].x], p2 = pt[g[i][j].x];
			if(p1 > base) u ^= 1;
			if(p2 > base) v ^= 1;
			merge(u, v);
		}
	}
  //x가 속한 평면의 번호 : find(x)
	for(int i=1; i<=m; i++){
		dual_pt.push_back(id[i << 1] = find(i << 1));
		dual_pt.push_back(id[i << 1 | 1] = find(i << 1 | 1));
	}
	compress(dual_pt);
  //id값 좌표 압축
	for(int i=1; i<=m; i++){
		id[i << 1] = lower_bound(all(dual_pt), id[i << 1]) - dual_pt.begin();
		id[i << 1 | 1] = lower_bound(all(dual_pt), id[i << 1 | 1]) - dual_pt.begin();
	}
  //듀얼 그래프 인접 리스트 생성
	for(int i=1; i<=m; i++){
		int u = id[i << 1];
		int v = id[i << 1 | 1];
		dual[u].emplace_back(v, i);
		dual[v].emplace_back(u, i);
	}
	for(int i=0; i<101010; i++) compress(dual[i]);
}

//다익스트라
//flag = 0이면 최솟값, flag = 1이면 최댓값
ll dst1[101010], dst2[101010];
void dijkstra(vector<p> g[101010], int s, int t, int flag){
	memset(dst1, 0x3f, sizeof dst1);
	priority_queue<p> pq;
	pq.emplace(0, s); dst1[s] = 0;
	while(pq.size()){
		ll now = pq.top().y;
		ll cst = -pq.top().x;
		pq.pop();
		if(dst1[now] - cst) continue;
		for(auto i : g[now]){
			if(dst1[i.x] > dst1[now] + w[i.y]){
				dst1[i.x] = dst1[now] + w[i.y];
				pq.emplace(-dst1[i.x], i.x);
			}
		}
	}
	if(flag == 0){ cout << dst1[t] << " "; return; }

	memset(dst2, 0x3f, sizeof dst2);
	pq.emplace(0, t); dst2[t] = 0;
	while(pq.size()){
		ll now = pq.top().y;
		ll cst = -pq.top().x;
		pq.pop();
		if(dst2[now] - cst) continue;
		for(auto i : g[now]){
			if(dst2[i.x] > dst2[now] + w[i.y]){
				dst2[i.x] = dst2[now] + w[i.y];
				pq.emplace(-dst2[i.x], i.x);
			}
		}
	}

	ll ans = 1e18;
	for(int i=1; i<=m; i++){
		int u = id[i << 1];
		int v = id[i << 1 | 1];
		ans = min(ans, dst1[u] + dst2[v]);
		ans = min(ans, dst1[v] + dst2[u]);
	}
	cout << sum - ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> pt[i].x >> pt[i].y;
	LU = ++n; LD = ++n; RU = ++n; RD = ++n;
	pt[LU] = p(pt[1].x, 1e10); //왼쪽 위
	pt[LD] = p(pt[1].x, -1e10); //왼쪽 아래
	pt[RU] = p(pt[n-4].x, 1e10); //오른쪽 위
	pt[RD] = p(pt[n-4].x, -1e10); //오른쪽 아래

	cin >> m;
	for(int i=1; i<=m; i++){
		int s, e; cin >> s >> e >> w[i]; sum += w[i];
		g[s].emplace_back(e, i);
		g[e].emplace_back(s, i);
	}
	LUE = ++m; w[m] = 3e9; g[1].emplace_back(LU, m); g[LU].emplace_back(1, m);
	LDE = ++m; w[m] = 3e9; g[1].emplace_back(LD, m); g[LD].emplace_back(1, m);
	RUE = ++m; w[m] = 3e9; g[n-4].emplace_back(RU, m); g[RU].emplace_back(n-4, m);
	RDE = ++m; w[m] = 3e9; g[n-4].emplace_back(RD, m); g[RD].emplace_back(n-4, m);
	UE = ++m; w[m] = 3e9; g[LU].emplace_back(RU, m); g[RU].emplace_back(LU, m);
	DE = ++m; w[m] = 3e9; g[LD].emplace_back(RD, m); g[RD].emplace_back(LD, m);
	getDual();

	dijkstra(g, 1, n-4, 0);
	int up = id[LUE << 1]; //위 영역
	int dw = id[LDE << 1]; //아래 영역
	dijkstra(dual, up, dw, 1);
}