A - Colorful MST

https://atcoder.jp/contests/cf17-tournament-round2-open/tasks/asaporo2_a

解法

難しいので、全頂点が無色の時を考える。

短い辺を貪欲にk-1個選んで1 - 2  , 2 - 3　のように繋げそう

しかし、閉路に含まれる辺をすべて選ぶ事はできないので、最小全域木に対してやらなければならない

いくつか塗られていると同じようには出来ない

上の赤い部分が実質的な閉路になっているが、グラフ上は閉路で無いためである

このような問題は同じ数字が複数あるため起きている

よって同じ色の頂点を一つにまとめれば、最小全域木から辺を貪欲に選べる

https://atcoder.jp/contests/cf17-tournament-round2-open/submissions/4744870

void solve() {
    cin >> n >> m >> k;
    na(a, n);
    digraph<> g(2 * k5);
    rep(i, m) {
        int f, t, c;
        cin >> f >> t >> c;
        --f, --t;
        if (a[f])f = a[f] + n;
        if (a[t])t = a[t] + n;
        g.add(f, t, c);
    }
    UnionFind uf(k5 * 2);
    g.set_edges();
    sort(g.edges);
    vi ed;
    fora(e, g.edges) {
        if (uf.same(e.f, e.t))con;
        uf.unite(e.f, e.t);
        ed += e.c;
    }
    if (sz(ed) < k - 1) {
        fin(-1);
    } else {
        cout << sum(ed, k - 1) << endl;
    }
}