AOJ 2390 AYBABTU

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390

解法

感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう．
そして投げたら通った（終了）…だと困るので厳密じゃないけど一応それっぽいのだけ．

木なので基地でパスを区切ったものを考えれば，max(パスのなかの辺の重み)の小さい方から k - 1 個使えば嬉しい．
これは普通に辺のコストをでかいほうから使っていくクラスカルの要領でやっていき，加えた辺を負の値と考えて答えから省くようにすると同じことができる．
加えようとする辺が基地と基地を結ぶようなものであるときは，それ以上くっつかれると困る場合は無視，そうでない場合は使って上限をへらせばよい．

ソースコード

#include <bits/stdc++.h>
using namespace std;

class union_find {
public:
    union_find(int n) : par(n, -1) {}
    int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
    void unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) return;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
private:
    vector<int> par;
};

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

int main() {
    int n, t, k;
    int cs = 1;
    while(cin >> n >> t >> k, n) {
        vector<edge> es(n - 1);
        int ans = 0;
        for(int i = 0; i < n - 1; ++i) {
            cin >> es[i].u >> es[i].v >> es[i].cost;
            es[i].u--; es[i].v--;
            ans += es[i].cost;
        }
        vector<bool> is_base(n);
        for(int i = 0; i < t; ++i) {
            int b; cin >> b;
            is_base[b - 1] = true;
        }
        sort(rbegin(es), rend(es));
        union_find uf(n);
        int can = t - k - 1;
        for(auto& e : es) {
            int u = uf.root(e.u), v = uf.root(e.v);
            if(is_base[u] && is_base[v]) {
                if(can > 0) {
                    can--;
                    ans -= e.cost;
                    uf.unite(u, v);
                }
            } else {
                uf.unite(u, v);
                ans -= e.cost;
                bool b1 = is_base[u], b2 = is_base[v];
                is_base[u] = is_base[u] | b2;
                is_base[v] = is_base[v] | b1;
            }
        }

        cout << "Case " << cs++ << ": " << ans << endl;
    }
}

感想

これはAOJ-ICPC700らしいんですが，体感300以下．厳密な証明が難しいから700？わからん．