問題

問題文

http://poj.org/problem?id=3380

問題概要

頂点数が n　 ${(1 \leqq n \leqq 10^{4} )}$ の重み付き無向グラフが与えられる。

各頂点は島を表しており, ある島から他の島までの経路は 1 通りしか存在しない。

各島には 1 つの町がある。

町には 1 から n まで番号がつけられており, 道路は 1 から n - 1 までの番号がついてる。

島の道路に k 個の橋を建設する。

島から島へ移動するとき普通の道路は馬でしか移動できない。一方, 橋を建設した道路は四輪馬車でのみ渡ることができる。

k 個の道路に橋を建設するとき全点対間の移動時間が最小となるような道路はどれか。

入力は次の形式で与えられる。

n k s_h s_c
b_1 e_1 l_1
b_2 e_2 l_2
...
b_n-1 e_n-1 l_n-1

n: 町の数, k: 橋の数 ${(1 \leqq k \lt n \leqq 10^{4} )}$

s_h: 馬の速さ, s_c: 四輪馬車の速さ ${(1 \leqq s_h, s_c \leqq 10^{5} )}$

b, e: 道路によってつながっている町の番号, l: 道路の距離

橋を建設すべき道路の番号を空白区切りで出力せよ。複数の解がある場合はどれを答えてもよい。

例

次のような入力が与えられたとき,

グラフは次のようになり

f:id:kira000:20180104052227p:plain

赤で示した辺 (番号で言えば 1 と 3) に橋を建設すると全点対間の移動時間が最小となるので

f:id:kira000:20180104052255p:plain

答えは

1 3

となる。

解答例

指針

DFS により全点対間を移動するときに各辺が使用される回数を求める。

解説

ある頂点から他の頂点までの経路は 1 通りしかないので与えられたグラフは閉路を持たない連結グラフ, 木となる。

全点間を移動するとき各辺が使用される回数を d_i, 各辺の長さを l_i としたとき,

s_h < s_c の場合

d_i * l_i の大きい順に k 個選んだものが最適解

s_h >= s_c の場合

d_i * l_i の小さい順に k 個選んだものが最適解

となる。

全点対間を移動するとき各辺が使用される回数の求め方

ある頂点を root とした DFS 木を考える。

各頂点 v に対して v の部分木のサイズを v_size とすると v_size は深さ優先探索 (Depth First Search: DFS) を用いて求めることができる。

各辺 e (p, c) について，p は c の親とすると辺 e が使われる回数は c_size * (n - c_size) * 2 となる。

例えば下のグラフの赤い辺 e (1, 2) が使われる回数は 2 * (6-2) * 2 = 16 となる。

f:id:kira000:20180104074343p:plain

今回は大小関係のみが重要であるから2倍する必要はない。

また解が複数ある場合はどれを出力しても良いので stable_sort() を使う必要もない。

// Memory: 2340K, Time: 469MS, Language: C++
#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX_N 10001

using namespace std;

// first->sum, second->id
typedef pair<long long, int> P;

struct Edge {
    long long to, len, id;
    Edge() {}
    Edge(long long a, long long b, long long c) : to(a), len(b), id(c) {}
};

// ある頂点を根としたときの各頂点の部分木のサイズをカウント
long long cnt[MAX_N];
int n, k;
vector<Edge> Tree[MAX_N];
vector<P> p;

// cur: 探索中の頂点, par: cur の親
int dfs(int cur, int par) {
    cnt[cur] = 1;
    for (int i = 0; i < Tree[cur].size(); i++) {
        Edge e = Tree[cur][i];
        if (e.to == par) { continue; }
        cnt[cur] += dfs(e.to, cur);
        p.push_back(P(e.len * cnt[e.to] * (n - cnt[e.to]), e.id));
    }
    return cnt[cur];
}

int main() {
    int s_h, s_c, b, e, l;

    scanf("%d %d %d %d", &n, &k, &s_h, &s_c);

    for (int i = 0; i < n - 1; i++) {
        scanf("%d %d %d", &b, &e, &l);
        b--; e--;
        Tree[b].push_back(Edge(e, l, i));
        Tree[e].push_back(Edge(b, l, i));
    }

    dfs(0, -1);

    sort(p.begin(), p.end());

    if (s_h < s_c) { reverse(p.begin(), p.end()); }

    for (int i = 0; i < k; i++) {
        printf("%d", p[i].second + 1);
        printf((i == k - 1) ? "\n" : " ");
    }

    return 0;
}

参考文献

大学の先輩のコード

kira924age’s note

POJ3380: Bridges

問題

問題文

問題概要

例

解答例

指針

解説

全点対間を移動するとき各辺が使用される回数の求め方

参考文献