Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 Regions

Category: JOI Tag: binary-search, dp

Regions

問題概要


頂点数Nの木構造で, 各辺には距離が与えられる.
この木をM個の木に分解するとき, それぞれの木の直径のうち最大のものを最小化しろ.

解法


距離を2分探索する.
木を根付き木と考えることにする. また頂点vから親への辺の長さをdist[v]とする.
ある直径x以内でM個の木に分割できるかは以下のDPを葉からしながら, 分割する回数を数えれば良い.

dp[v] = 頂点vを含む分割された木のうち, vから葉までの最長の距離

頂点vからその親uに辺を伸ばすとき
dp[v]+dist[v]がxを超えるならその辺で分割.
dp[u]+dp[v]+dist[v]がxを超えるなら, 小さくなる方だけ繋いで大きい方の辺で分割(これは直径の両端がv以外でvで折れた形になってるやつ).
それ以外ならそのまま繋いでmax(dp[u], dp[v]+dist[v])

この分割数がM回未満だったら直径x以内でM個の木に分割できる.

コード


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

int n, m;
vector<pair<int,int>> G[1<<15];
vector<int> vs;
int dep[1<<15], dp[1<<15], par[1<<15], dist[1<<15];

void dfs(int v, int u, int d)
{
        dep[v] = d;
        par[v] = u;
        for(auto &p: G[v]) {
                if(p.first == u) continue;
                dist[p.first] = p.second;
                dfs(p.first,v,d+1);
        }
}

bool cmp(const int &u, const int &v)
{
        return dep[u] > dep[v];
}

bool ok(int x)
{
        memset(dp,0,sizeof(dp));
        int cnt = 0;
        for(auto &v: vs) {
                int &u = par[v];

                if(dp[v]+dist[v] > x) cnt++;
                else if(dp[u] + dp[v] + dist[v] > x) {
                        cnt++;
                        dp[u] = min(dp[u], dp[v]+dist[v]);
                }
                else dp[u] = max(dp[u], dp[v]+dist[v]);
        }
        return cnt < m;
}

int solve()
{
        dfs(0,-1,0);
        for (int i = 1; i < n; i++) vs.push_back(i);
        sort(begin(vs),end(vs),cmp);

        int lb = -1, ub = n*100, mid;
        while(ub-lb>1) {
                mid = (lb+ub)>>1;
                if(ok(mid)) ub = mid;
                else lb = mid;
        }
        return ub;
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < n-1; i++) {
                int u, v, d;
                cin >> u >> v >> d;
                u--; v--;
                G[u].push_back(make_pair(v,d));
                G[v].push_back(make_pair(u,d));
        }

}

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

Comments