TopCoder SRM 710 Div2 Hard MinMaxMax

問題概要

頂点数 N, 辺の数がM の連結グラフが与えられる.
それぞれの頂点と辺には重みがつけられていて,i 番目の頂点の重みは vi, i 番目の頂点の重みは wi である.
異なる2つの頂点 u, v の間のコストを,u-v パスのうちで,(パスに含まれる頂点の重さの最大値) * (パスに含まれる辺の重さの最大値) の最小値と定義する.
各 (u, v) に対するコストの総和を求めよ.

・制約
2 <= N <= 300
N-1 <= M <= min(2500, N(N-1)/2)
1 <= wi <= 10^6
1 <= vi <= 10^6
多重辺やループは存在しない.

解法の前に

自分は,最初「ワーシャルフロイドの要領でやるんだろうな~」と思って色々考えてみたものの,実装方針が思いつかず,普段理解せずに使ってたんだなぁと痛感した.(結局解けなかった).

writer解では2つのアプローチが紹介されていて,1つめは Kruskal 法の要領でやっていくもので,2つめはワーシャルフロイドの要領でやっていくものだった.
両方記事にしたいけど,まとめると長いので2つに分ける.
今回は1つ目のアプローチを実装した.

解法1

頂点の重みと辺の重みのどちらも考える必要があるので大変.(単純に,ある頂点に来るための最小コストだけを保存していくような最短経路問題ではない).
なので,とりあえず頂点の最大の重みを固定してしまってから考えると良い.これを vmax とする.
その上で,辺の重みが小さい順にソートしておいて,小さい方から追加していく.この時,辺を追加することで結ばれた連結成分を union-find 木で保存しておく(Kruskal 法と同じ).

追加したい辺が頂点 ai と bi を結んでいたとする.
ai と bi がすでに同じ連結成分に含まれれば,その辺は無視できる(より小さい辺のみでつながっている).また,ai と bi の重みのどちらかが vmax を超えても,その辺を無視する.
それ以外の場合,その辺を追加する.
この時,ai の連結成分 S1 と,bi の連結成分 S2 の各頂点間 (s, t) (s ∈ S1, t ∈ S2) のコストは vmax * (今追加した辺の重み) 以下となることがわかる.なぜなら,S1 と S2 に含まれる頂点の重みは全て vmax 以下であり,かつ今までに追加した全ての辺の重みは,今追加した辺の重みよりも小さいからである.
よって,vmax * (今追加した辺の重み) と,今までにわかっている (s, t) 間の最小コストとを比べて,小さい方を保存しておけばよい.

これを vmax を N 個の頂点で全部試せば,目的の値が得られる.

計算量は O(N^2M) か?これはちょっと自信がない(連結成分のコスト更新の二重ループのコストがピンとこない.下のコードでいうと,va と vb でループを回しているところ.)

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

constexpr ll INF = 1e18;

class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }

    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) { // size(x) > size(y)
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return -par_[root(x)];
    }

private:
    std::vector<int> par_;
};

class MinMaxMax {
public:
    ll findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) {
        const int N = v.size(), M = w.size();
        vector<vector<ll>> d(N, vector<ll>(N, INF));
        vector<P> ww(M);
        for(int i=0; i<M; ++i) {
            ww[i] = make_pair(w[i], i);
        }
        sort(ww.begin(), ww.end());
        for(int i=0; i<N; ++i) {
            vector<int> comp(N);
            union_find uf(N);
            for(int j=0; j<M; ++j) {
                int aa = a[ww[j].second], bb = b[ww[j].second];
                if(uf.same(aa, bb) || v[i] < v[aa] || v[i] < v[bb]) {
                    continue;
                }
                ll now = v[i] * ww[j].first;
                vector<int> va, vb;
                for(int k=0; k<N; ++k) {
                    if(uf.same(k, aa)) {
                        va.push_back(k);
                    } else if(uf.same(k, bb)) {
                        vb.push_back(k);
                    }
                }
                for(int k=0; k<va.size(); ++k) {
                    for(int l=0; l<vb.size(); ++l) {
                        int ca = va[k], cb = vb[l];
                        d[ca][cb] = min(now, d[ca][cb]);
                        d[cb][ca] = min(now, d[cb][ca]);
                    }
                }
                uf.unite(aa, bb);
            }
        }
        ll res = 0;
        for(int i=0; i<N; ++i) {
            for(int j=i+1; j<N; ++j) {
                res += d[i][j];
            }
        }
        return res;
    }
};

解法2

わかりやすい記事があったので,引用して終わりとします.
kmjp.hatenablog.jp