백준12766 지사 배정

작성일 | In

문제 링크

  • http://icpc.me/12766

문제 출처

  • 2016 ACM-ICPC World Final B번

사용 알고리즘

  • DnC Opt

시간복잡도

  • $O(SB log B)$

풀이

$i$번 정점이 크기가 $K_i$인 그룹에 속해있다고 하면, $i$번 정점이 전체 비용에 $(K_i - 1)(dist(i, B+1)+dist(B+1, i))$ 만큼 영향을 줍니다.
위 식을 보면, $i$번 정점이 비용에 영향을 주는 양은 그룹의 크기에만 영향을 받는다는 것을 알 수 있습니다.

만약 $S$개의 그룹의 크기가 모두 정해졌다면, $val(i) = dist(i, B+1)+dist(B+1, i)$가 작은 정점이 큰 그룹에 들어가고, $val(i))$값이 큰 정점이 작은 그룹에 들어가는 것이 최적입니다. 그러므로 $val(i)$값을 기준으로 정렬을 하고, 연속한 정점끼리 그룹을 묶어도 정답을 찾을 수 있습니다.

$D(g, i)$를 $val(~)$ 값이 작은 $i$개의 정점을 $g$개의 그룹으로 묶은 최소 비용이라고 정의하면, $D(g, i) = min_{k < i}(D(g-1, k)+(i-k-1)(\space val(k+1)+val(k+2)+…+val(i)) \space)$로 상태 전이에 대한 식을 새울 수 있습니다.

$O(SB^2)$ DP처럼 보이지만, $C(i, k) = (i-k-1)(val(k+1)+val(k+2)+…+val(i))$가 사각 부등식을 만족하므로 DnC Opt를 사용해 $O(SB log B)$ 복잡도로 풀 수 있습니다.

전체 코드

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;
typedef pair<ll, ll> p;

int n, b, s, r; //교차로, 지사, 프로젝트, 도로

vector<p> g[5050], rg[5050];
ll d[5050], rd[5050];

ll dp[5050][5050], opt[5050][5050];
ll val[5050], sum[5050];

void dijkstra(int st, vector<p> g[5050], ll dst[5050]){
	priority_queue<p> pq; pq.push({ 0, st }); dst[st] = 0;
	while (pq.size()){
		ll now = pq.top().second;
		ll cst = -pq.top().first;
		pq.pop();
		if (cst > dst[now]) continue;
		for (auto i : g[now]){
			ll nxt = i.first;
			ll nxtCst = i.second + cst;
			if (nxtCst < dst[nxt]){
				dst[nxt] = nxtCst;
				pq.push({ -nxtCst, nxt });
			}
		}
	}
}

ll cst(int a, int b){
	return (sum[b] - sum[a]) * (b - a - 1);
}

void go(int t, int s, int e, int l, int r){
	if (s > e) return;
	int m = s + e >> 1;
	dp[t][m] = opt[t][m] = -1;
	for (int k = l; k <= min(m - 1, r); k++){
		ll now = dp[t - 1][k] + cst(k, m);
		if (dp[t][m] == -1 || dp[t][m] > now){
			dp[t][m] = now; opt[t][m] = k;
		}
	}
	go(t, s, m - 1, l, opt[t][m]);
	go(t, m + 1, e, opt[t][m], r);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> b >> s >> r;
	for (int i = 0; i < r; i++){
		int s, e, x; cin >> s >> e >> x;
		g[s].push_back({ e, x });
		rg[e].push_back({ s, x });
	}
	memset(d, 0x3f, sizeof d);
	memset(rd, 0x3f, sizeof rd);
	dijkstra(b + 1, g, d);
	dijkstra(b + 1, rg, rd);
	for (int i = 1; i <= b; i++){
		val[i] = d[i] + rd[i];
	}
	sort(val + 1, val + b + 1);
	for (int i = 1; i <= b; i++){
		sum[i] = sum[i - 1] + val[i];
	}
	for (int i = 1; i <= b; i++){
		dp[1][i] = sum[i] * (i - 1);
		opt[1][i] = 1;
	}
	for (int i = 2; i <= s; i++){
		go(i, i, b, 0, b);
	}
	cout << dp[s][b];
}