백준16127 미생물 키우기

작성일 | In

문제 링크

  • http://icpc.me/16127

사용 알고리즘

  • DMST

시간복잡도

  • $O(N^3)$

풀이

모든 미생물을 하나씩 만들면, 나머지를 만드는 최소 비용을 구하는 것은 쉽습니다. 모든 미생물을 하나씩 만드는 최소 비용을 구하는 방법을 알아봅시다.

$N+1$번 미생물을 추가해서, 처음에 $N+1$번 미생물 하나만 있다고 생각해봅시다. 그러면 입력으로 주어진 $y_i$를 $z_{N+1, i}$, $z_{i, N+1} = \infty$로 해석할 수 있습니다.
결국 이 문제는 루트가 정점이 $N+1$개 있는 완전 그래프에서, 루트가 $N+1$인 Directed MST를 구하는 문제가 됩니다.

Directed MST의 가중치는 $O(VE)$에 구할 수 있으므로 문제를 해결할 수 있습니다.
$O(VE \log E)$에 푸는 방법도 있다고 합니다.

전체 코드

DMST code : https://gina65.tistory.com/23

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

struct Edge{
    ll s, e, x;
    Edge() = default;
    Edge(ll s, ll e, ll x) : s(s), e(e), x(x) {}
};

ll DirectedMST(int N, vector<Edge> edge, int root){
    vector<int> ID(N+1); // compressed node's id
    vector<int> minNode(N+1);
    vector<ll> minCost(N+1);

    ll ret = 0;
    while(true){
        fill(all(ID), 0);
        fill(all(minCost), 0x3f3f3f3f3f3f3f3f);
        for(const auto &i : edge){
            if(i.s != i.e && i.x < minCost[i.e]) minNode[i.e] = i.s, minCost[i.e] = i.x;
        }
        minCost[root] = 0;
        for(int i=1; i<=N; i++) ret += minCost[i];

        int pv = 0;
        ID[root] = ++pv;
        for(int i=1, j; i<=N; i++){
            if(ID[i]) continue;
            for(j=i; !ID[j]; j=minNode[j]) ID[j] = -1;
            if(ID[j] == -1){
                pv++;
                for(; ID[j]==-1; j=minNode[j]) ID[j] = pv;
            }
            for(j=i; ID[j]==-1; j=minNode[j]) ID[j] = ++pv;
        }

        if(N == pv) break; N = pv;
        for(auto &i : edge){
            i.x -= minCost[i.e];
            i.s = ID[i.s];
            i.e = ID[i.e];
        }
        root = ID[root];
    }
    return ret;
}

int N;
ll X[333], Y[333], Z[333][333], mn[333];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> X[i];
    for(int i=1; i<=N; i++) cin >> Y[i];
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) cin >> Z[i][j];

    memcpy(mn, Y, sizeof mn);
    for(int i=1; i<=N; i++) Z[N+1][i] = Y[i];
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) mn[j] = min(mn[j], Z[i][j]);

    vector<Edge> edges;
    for(int i=1; i<=N; i++) edges.emplace_back(N+1, i, Y[i]);
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) edges.emplace_back(i, j, Z[i][j]);
    ll res = DirectedMST(N+1, edges, N+1);

    for(int i=1; i<=N; i++) res += (X[i] - 1) * mn[i];
    cout << res;
}