mayoko’s diary

プロコンとかいろいろ。

SRM 692 div1 easy HardProof

問題

TopCoder Statistics - Problem Statement

N 頂点の有向グラフが与えられる(各頂点 i からは i 以外のすべての頂点にむかってあるコストの辺が張ってある)。
ここから適切な辺を選び, N 頂点をすべて強連結にしたい。この条件を満たすもとで, (選ばれる辺のコストの最大値) - (選ばれる辺のコストの最小値) を最小にしたい。このコストの値を求めよ。

解法

問題内容を上のように要約できればもう簡単かもしれません。

最小のコストの辺を low として, そこから low+diff の辺までは許容する場合, 全ての頂点が強連結になるかを diff について二分探索しながら判定していきます。

N = 30 とかにして SCC ライブラリ持ってなくてもわーしゃるしても普通に通るようにしても良かったと思うんですけどどうなんでしょう。

struct SCC {
    int V;
    vector<vi> G, rG;
    vector<int> vs, used, cmp;
    SCC(const vector<vi>& g) : V(g.size()), G(g), rG(V), used(V), cmp(V) {
        for (int i = 0; i < V; i++) for (int u : G[i]) rG[u].push_back(i);
    }
    void dfs(int v) {
        used[v] = 1;
        for (int u : G[v]) if (!used[u]) dfs(u);
        vs.push_back(v);
    }
    void rdfs(int v, int k) {
        used[v] = 1;
        cmp[v] = k;
        for (int u : rG[v]) if (!used[u]) rdfs(u, k);
    }
    int calc() {
        fill(used.begin(), used.end(), 0);
        vs.clear();
        for (int v = 0; v < V; v++) {
            if (!used[v]) dfs(v);
        }
        fill(used.begin(), used.end(), 0);
        int k = 0;
        for (int i = vs.size()-1; i >= 0; i--) {
            if (!used[vs[i]]) rdfs(vs[i], k++);
        }
        return k;
    }
};

int N;
bool ok(int low, int diff, const vi& D) {
    vector<vi> G(N);
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (i != j) {
        if (low <= D[i*N+j] && D[i*N+j] <= low+diff) {
            G[i].push_back(j);
        }
    }
    SCC scc(G);
    return scc.calc() == 1;
}

class HardProof {
public:
    int minimumCost(vector <int> D) {
        const int INF = 200000;
        N = 0;
        while (N*N < D.size()) N++;
        vector<int> vs = D;
        sort(vs.begin(), vs.end());
        vs.erase(unique(vs.begin(), vs.end()), vs.end());
        int ans = INF;
        for (int el : vs) {
            int low = -1, high = INF;
            while (high-low > 1) {
                const int med = (low+high)/2;
                if (ok(el, med, D)) high = med;
                else low = med;
            }
            ans = min(ans, high);
        }
        return ans;
    }
};