問題文が難しい。

problem

島が$N$個あり、それぞれ時刻$h_i$に沈む。$M$種の橋を建設できる。 橋の建設計画を決め、その時点で残っている島が連結であるような最後の時刻を最大化し、複数あるなら費用も最小化せよ。

solution

逆から見る。Prim法っぽく。$O(M + N \log N)$。

まず非連結になる時刻を求める。これは全ての橋を建設するとし、島は逆から浮かび上がってくるものとして見れば求まる。 この非連結になる時刻から始めて同様に島を浮かび上がらせながら、各時点で連結になるように橋を建設していけば終わり。

implementation

#include <algorithm>
#include <cstdio>
#include <map>
#include <numeric>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using namespace std;
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

template <typename T>
map<T, int> coordinate_compression_map(vector<T> const & xs) {
    int n = xs.size();
    vector<int> ys(n);
    iota(whole(ys), 0);
    sort(whole(ys), [&](int i, int j) { return xs[i] < xs[j]; });
    map<T,int> f;
    for (int i : ys) {
        if (not f.count(xs[i])) { // make unique
            int j = f.size();
            f[xs[i]] = j; // f[xs[i]] has a side effect, increasing the f.size()
        }
    }
    return f;
}

struct disjoint_sets {
    vector<int> data;
    disjoint_sets() = default;
    explicit disjoint_sets(size_t n) : data(n, -1) {}
    bool is_root(int i) { return data[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); }
    int set_size(int i) { return - data[find_root(i)]; }
    int unite_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data[i] += data[j];
            data[j] = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

int main() {
    while (true) {
        // input
        int n, m; scanf("%d%d", &n, &m);
        if (n == 0 and m == 0) break;
        vector<int> h(n);
        repeat (i, n) {
            scanf("%d", &h[i]);
        }
        vector<vector<tuple<int, int, int> > > edges(n);
        repeat (i, m) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c); -- a; -- b;
            edges[a].emplace_back(c, a, b);
            edges[b].emplace_back(c, b, a);
        }
        // solve
        auto compress = coordinate_compression_map(h);
        vector<vector<int> > groups(compress.size());
        repeat (i, n) {
            groups[compress[h[i]]].push_back(i);
        }
        reverse(whole(groups));
        auto rise = [&](vector<int> const & group, vector<bool> & risen, reversed_priority_queue<tuple<int, int, int> > & que) {
            for (int i : group) {
                risen[i] = true;
            }
            for (int i : group) {
                for (auto edge : edges[i]) {
                    int j = get<2>(edge);
                    if (risen[j]) {
                        que.push(edge);
                    }
                }
            }
        };
        auto connect = [&](disjoint_sets & ds, vector<bool> const & risen, reversed_priority_queue<tuple<int, int, int> > & que) {
            int result = 0;
            while (not que.empty()) {
                int c, a, b; tie(c, a, b) = que.top();
                que.pop();
                if (not ds.is_same(a, b)) {
                    ds.unite_sets(a, b);
                    result += c;
                }
            }
            return result;
        };
        int disconnected = -1; {
            const int root = groups[0][0];
            int size = 0;
            vector<bool> risen(n);
            disjoint_sets ds(n);
            reversed_priority_queue<tuple<int, int, int> > que;
            repeat (t, groups.size()) {
                auto const & group = groups[t];
                rise(group, risen, que);
                connect(ds, risen, que);
                size += group.size();
                if (ds.set_size(root) != size) {
                    disconnected = t;
                }
            }
        }
        disconnected = min<int>(groups.size(), disconnected + 2);
        int result = 0; {
            vector<bool> risen(n);
            reversed_priority_queue<tuple<int, int, int> > que;
            repeat (t, disconnected) {
                auto const & group = groups[t];
                rise(group, risen, que);
            }
            disjoint_sets ds(n);
            result += connect(ds, risen, que);
            repeat_from (t, disconnected, groups.size()) {
                auto const & group = groups[t];
                rise(group, risen, que);
                result += connect(ds, risen, que);
            }
            if (ds.set_size(0) != n) result = 0;
        }
        // output
        printf("%d\n", result);
    }
    return 0;
}