백준18596 Monster Hunter

작성일 | In

문제 링크

  • http://icpc.me/18596

사용 알고리즘

  • 그리디
  • 유니온 파인드

시간복잡도

  • $O(N log N)$

풀이

모든 정점의 부모가 루트인 star graph를 생각해봅시다.

$b_i - a_i ≥ 0$인 정점을 $b_i - a_i < 0$인 정점보다 먼저 방문하는 것이 무조건 이득입니다.
$b_i - a_i ≥ 0$인 정점들 중에서는 $a_i$가 작은 정점(체력이 덜 감소하는 곳)부터 방문하는 것이 이득이고, $b_i - a_i < 0$인 정점들 중에서는 $b_i$가 큰 것(체력이 더 증가하는 곳)부터 방문하는 것이 이득입니다. 이것은 체력 변화에 대해서 그래프를 그려보면 쉽게 알 수 있습니다.

이 풀이를 일반적인 트리로 확장해봅시다.
아직 방문하지 않은 정점 중에서 i번 정점으로 가는 것이 가장 이득이라면, i의 부모를 방문한 이후에 바로 i번 정점으로 가는 것이 최적이기 때문에 i번 정점과 i의 부모 정점을 합쳐줄 수 있습니다. 이런 식으로 계속 정점을 합쳐주게 되면 최종적으로 1개의 정점만 남게 됩니다.

정점을 합치는 것은 union-find로, 가장 이득인 정점을 뽑는 것은 pq로 처리할 수 있습니다.

AGC023F와 비슷한 문제입니다. 풀이

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Node{
	ll a, b, i;
	bool operator < (const Node &t) const {
		ll aa = b - a, bb = t.b - t.a;
		if(aa >= 0 && bb < 0) return 0;
		if(aa < 0 && bb >= 0) return 1;
		if(aa < 0){
			return b < t.b;
		}
		return a > t.a;
	}
}node[101010];

priority_queue<Node> pq;

int par[101010];
int find(int v){
	return v == par[v] ? v : par[v] = find(par[v]);
}

vector<int> g[101010];
int p[101010], chk[101010];

void dfs(int v, int b){
	for(auto i : g[v]){
		if(b != i) continue;
		p[i] = v;
		dfs(i, v);
	}
}

void init(int n){
	for(int i=1; i<=n; i++) par[i] = i, g[i].clear(), chk[i] = 0;
}

void solve(){
	int n; cin >> n;
	init(n);
	node[1] = {0, 0, 1};
	for(int i=2; i<=n; i++){
		cin >> node[i].a >> node[i].b;
		node[i].i = i;
		if(i != 1) pq.push(node[i]);
	}
	for(int i=1; i<n; i++){
		int s, e; cin >> s >> e;
		g[s].push_back(e); g[e].push_back(s);
	}
	dfs(1, -1);

	while(pq.size()){
		auto t = pq.top(); pq.pop();
		int now = t.i;
		if(chk[now]) continue;
		chk[now] = 1;
		int nxt = find(p[now]);
		ll aa = min(-node[nxt].a, -node[nxt].a + node[nxt].b - node[now].a);
		ll bb = -node[nxt].a + node[nxt].b - node[now].a + node[now].b;
		bb = bb - aa;
		aa *= -1;
		node[nxt].a = aa; node[nxt].b = bb;
		par[now] = nxt;
		if(nxt != 1) pq.push(node[nxt]);
	}
	if(node[1].a < 0) exit(-1);
	cout << node[1].a << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}