Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 Finals

Category: JOI Tag: spanning-tree, union-find

Finals

問題概要


辺にコストのある無向グラフが与えられる.
各頂点からK個の頂点を選んだとき, どの頂点もそのいずれかに到達できるように辺を選ぶ.
使う辺のコストの和の最小を求めよ.

解法


Kruskal法で最小全域木を求める要領でやる.
今回は全域木ではなくてK個の木からなる全域森を考えれば良い.
コストの小さい辺から選んでコストを足していき, 連結成分がK個になったら終了

コード


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

struct union_find
{
        vector<int> rnk, par;

        union_find(int n){
                rnk.assign(n,1);
                par.assign(n,0);
                for(int i = 0; i < n; i++) par[i] = i;
        }

        int find(int x) {
                if(x == par[x]) return x;
                else return par[x] = find(par[x]);
        }
        void unite(int x, int y) {
                x = find(x); y = find(y);
                if(x == y) return;
                if(rnk[x] > rnk[y]) par[y] = x;
                else {
                        par[x] = y;
                        if(rnk[x] == rnk[y]) rnk[y]++;
                }
        }
        bool same(int x, int y){ return find(x)==find(y);}
};

struct edge
{
        int u, v, c;
        bool operator<(const edge &e)const{ return c < e.c;}
};

int n, m, k;
vector<edge> es;

int solve()
{
        sort(begin(es),end(es));
        union_find uf(n);
        int f = n, ans = 0;
        for(auto &e: es) {
                if(f <= k) break;
                if(uf.same(e.u,e.v)) continue;
                uf.unite(e.u,e.v);
                f--;
                ans += e.c;
        }
        return ans;
}

void input()
{
        cin >> n >> m >> k;
        for (int i = 0; i < m; i++) {
                int u, v, c;
                cin >> u >> v >> c;
                es.push_back((edge){u-1,v-1,c});
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments