백준13361 최고인 대장장이 토르비욘

작성일 | In

문제 링크

  • http://icpc.me/13361

문제 출처

  • 2016 NCPC H번

사용 알고리즘

시간복잡도

풀이

여름학교에서 못 풀고, 집에서도 못 풀어서 구사과님의 풀이를 봤습니다ㅠㅠ

철판의 방향을 고정시킨 상황을 가정해봅시다.
이 상황에서는 철판의 넓이가 줄어들어야 한다는 사실은 필요 없습니다. 정렬을 하면 넓이가 감소하도록 조절할 수 있습니다.
그러므로 방향이 고정되었을 때, 넓이가 모두 다르다면 아무 상관 없습니다.
결국, 철판의 방향을 적절히 고정시켜서 모든 넓이를 다르게 하고 높이를 최대화/너비의 합을 최소화시키는 문제로 바뀌게 됩니다.

넓이와 높이를 나타내는 숫자를 정점으로 잡고, 한 철판의 높이와 넓이를 나타내는 두 정점을 서로 이어준 그래프를 생각해봅시다.
최대 2N개의 정점으로 이루어진 그래프가 나오게 됩니다. 우리는 아래 3가지 조건을 만족하는 상태를 찾으면 됩니다.

  • 각 간선에 달려있는 정점 중 하나를 색칠하고
  • 색칠한 정점이 겹치면 안 되고
  • 색칠한 정점의 가중치의 합은 최소화해야한다.
입력 조건을 보면 항상 답이 존재한다고 나와있기 때문에, 모든 컴포넌트는 E <= V 를 만족합니다. 그러므로 각 컴포넌트는 두 가지 상태 중 하나입니다.

  1. 트리 하나의 정점만 안 색칠하면 됩니다. 가중치를 최소화할 것이기 때문에 가중치가 가장 큰 정점을 색칠하지 않으면 됩니다.
    해당 컴포넌트의 가중치의 합은 (전체 가중치의 합) - (최대 가중치)입니다.

  2. |V| = |E| 모든 정점을 색칠할 수 있습니다. 이 컴포넌트의 합은 전체 가중치의 합이 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define int long long
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n;
vector<p> v;
vector<ll> comp;
vector<int> g[505050];
ll ans;

int par[505050];
ll mx[505050];
ll sum[505050];
int cycle[505050];

void init(){
	for(int i=0; i<comp.size(); i++) par[i] = i, mx[i] = comp[i], sum[i] = comp[i];
}

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

bool merge(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return 0;
	par[u] = v;
	mx[v] = max(mx[u], mx[v]);
	sum[v] += sum[u];
	cycle[v] = cycle[u] || cycle[v];
	return 1;
}

int idx(ll x){
	return lower_bound(all(comp), x) - comp.begin();
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n); comp.reserve(n << 1);
	for(auto &i : v){
		cin >> i.x >> i.y;
		comp.push_back(i.x); comp.push_back(i.y);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());
	for(auto i : v){
		g[idx(i.x)].push_back(idx(i.y));
		g[idx(i.y)].push_back(idx(i.x));
	}
	init();
	for(int i=0; i<n; i++){
		ll x = idx(v[i].x);
		ll y = idx(v[i].y);
		if(!merge(x, y)){
			cycle[find(x)] = 1;
		}
	}
	for(auto i : v){
		ans += i.x + i.y;
	}
	for(int i=0; i<comp.size(); i++){
		if(i != find(i)) continue;
		if(cycle[i]) ans -= sum[i];
		else ans -= sum[i] - mx[i];
	}
	cout << ans;
}