TopCoder SRM 692 Div1 Easy: HardProof

,

I tried to use my SCC library, but it causes TLE.

problem

重み付き有向グラフで、任意の異なる頂点間のそれぞれの方向に辺がちょうど$1$本あるものが与えられる。つまり$|E| = {|V|}^2$となっている。 このグラフから適当に辺を選んで$|V|$個の頂点全体が強連結になるようにするとき、選んだ辺の重みの最大値と最小値の差の最小値を答えよ。

$\operatorname{ans} = \min \{ \max X - \min X \mid X \subseteq E, X \operatorname{strongly connects} V \}$.

solution

For each edge $e$, assume the edge $e$ is the lowest-weight one, and find the minimum cost $k$ to connect $V$ strongly. Add edges greedily like Dijkstra, and check the connectivity using DFS with memoization. This seems $O(N^5)$.

You must take care about the case $N = 1$.

implementation

#include <bits/stdc++.h>
#include <functional>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <class T> bool setmin(T & l, T const & r) { if (not (r < l)) return false; l = r; return true; }
class HardProof { public: int minimumCost(vector<int> D); };

const int inf = 1e9+7;
int HardProof::minimumCost(vector<int> D) {
    int n = sqrt(D.size());
    if (n == 1) return 0;
    auto cost = [&](int x, int y) { return D[x * n + y]; };
    int ans = inf;
    repeat (fst,n) {
        repeat (snd,n) if (fst != snd) {
            vector<bool> used(n);
            int used_count = 0;
            vector<vector<int> > g(n);
            vector<bool> connected(n);
            connected[fst] = true;
            int connected_count = 1;
            function<bool (int, vector<bool> &)> connect = [&](int x, vector<bool> & visited) {
                if (connected[x]) return true;
                visited[x] = true;
                for (int y : g[x]) if (not visited[y]) {
                    if (connect(y, visited)) {
                        connected[x] = true;
                        connected_count += 1;
                        return true;
                    }
                }
                return false;
            };
            int non_connected_iter = 0;
            priority_queue<tuple<int,int,int> > que; // (- cost, u, v)
            que.emplace(- (-1), fst, fst);
            que.emplace(- (-1), snd, snd);
            int max_cost = -1;
            while (not que.empty()) {
                int cur_cost, x, y; tie(cur_cost, x, y) = que.top(); que.pop(); cur_cost *= -1;
                setmax(max_cost, cur_cost);
                if (x != y) {
                    g[x].push_back(y);
                }
                if (not used[y]) {
                    used[y] = true;
                    used_count += 1;
                    repeat (z,n) if (z != y and cost(fst, snd) <= cost(y, z)) {
                        que.emplace(- cost(y, z), y, z);
                    }
                }
                if (used_count == n) {
                    while (non_connected_iter < n) {
                        vector<bool> visited(n);
                        if (connect(non_connected_iter, visited)) {
                            non_connected_iter += 1;;
                        } else {
                            break;
                        }
                    }
                }
                if (connected_count == n) {
                    break;
                }
            }
            if (connected_count == n) {
                setmin(ans, max_cost - cost(fst, snd));
            }
        }
    }
    return ans;
}