Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Joitter

Category: JOI Tag: spanning-tree

Joitter

問題概要


SNSサービスJoitterでは投稿の公開範囲を友達のみ, 友達とその友達のみ, 全体の3つから選べる.
また友達になるにはその組ごとに決まったコストがかかる.
N人の公開範囲と互いの友達登録コストが与えられたとき, 最小で何回友達になれば全員が互いに投稿を見ることができるようになるか.
またそのときの最小のコストを求めよ.

解法


問題自体は難しくないが, どのようなときに最適になるのか漏れ無くきちんと考察する必要がある.

友達関係のグラフを考える.
まず公開範囲が距離1の人だけの人がいる場合, その人と他全員が友達にならなければならない.
またこのとき互いは距離2以下に収まる連結なグラフになるので他の公開範囲については考えなくて良い.

公開範囲が距離2以下の人だけの人がいる場合, ある人を仲介にしてそこから他の人に辺を伸ばして木を作るのがほとんどの場合で最適.
ただし公開範囲が距離2以下の人だけの人がちょうど2人のとき(他の人は全体に公開), この2人を中心として他の人をどちらかコストの小さい方に繋ぐのが最適になる.
当然これらは連結なので全体に公開する人のことは考えなくて良い.

最後に公開範囲が全体の人だけの場合, 最小全域木を作るのが最適. これはprim法でやるのが楽で良い.

コード


(joitter.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n, c[1024][1024], p[1024], type[4], done[1024];

void type1()
{
        int cnt = 0, cst = 0;
        for (int i = 0; i < n; i++)
                if(p[i] == 1)
                        for (int j = 0; j < n; j++)
                                if(j != i and c[i][j] >= 0) {
                                        cst += c[i][j];
                                        cnt++;
                                        c[i][j] = c[j][i] = -1;
                                }
        cout << cnt << " " << cst << endl;
}

void type2()
{
        int cst = 1e9;
        for (int i = 0; i < n; i++){
                int tmp = 0;
                for (int j = 0; j < n; j++) tmp += c[i][j];
                cst = min(cst , tmp);
        }
        if(type[2] == 2) {
                int v[2] = {}, k = 0;
                for (int i = 0; i < n; i++) if(p[i] == 2) v[k++] = i;
                assert(k==2);
                int tmp = c[v[0]][v[1]];
                for (int i = 0; i < n; i++)
                        if(i != v[0] and i != v[1])
                                tmp += min(c[v[0]][i], c[v[1]][i]);
                cst = min(cst, tmp);
        }
        cout << n-1 << " " << cst << endl;
}

void type3()
{
        priority_queue<pii, vector<pii>, greater<pii> > q;
        q.push(pii(0,0));
        int cst = 0;
        while(!q.empty()){
                int cs = q.top().first, v = q.top().second;
                q.pop();
                if(done[v]) continue;
                done[v] = 1;
                cst += cs;
                for(int i = 0; i < n; i++)
                        if(!done[i]) q.push(pii(c[v][i], i));
        }
        cout << n-1 << " " << cst << endl;
}

void solve()
{
        if(type[1]) type1();
        else if(type[2]) type2();
        else type3();
}

void input()
{
        cin >> n;
        for (int i = 0; i < n; i++) {
                cin >> p[i];
                type[p[i]]++;
        }
        for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                        cin >> c[i][j];
}

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

Comments