読者です 読者をやめる 読者になる 読者になる

TCO2015 Round2A Div1 Med FoxMeeting

本番で解けなかったので復習をしました.
問題文を誤読してました(the total total distance ?).
まったく分からなかったのでsemiexpさんのソースコードを参考にしました.
(これを本番で通せる人々は凄いな)

[Med: FoxMeeting ]

問題

頂点数nの辺重み付き木とキツネがいる頂点番号の配列foxesが与えられる.
はじめに各々のキツネは異なる頂点にいる.
すべてのキツネはお互いに連絡が出来るように移動したい.
すべてのキツネがお互いに連絡できるとは移動した後にいる頂点部分集合によって誘導される部分グラフが連結であることである.
このとき、キツネは同じ頂点に移動しても良い.
目的はすべてのキツネがお互いに連絡できるように移動したときに各々の移動距離の最大値を最小化することである.

[制約]
1 <= n <= 50, 1 <= 辺の重みL <= 100000, 1 <= foxes.size <= n

解法

各々のキツネの移動距離がlen以内でお互いが連絡できるように移動することができるかを判定する問題を考えます.
もし、この判定に時間がかからなければ、移動距離の上限lenに対する二分探索で答えを求めることが出来ます.
二分探索にかかる時間はだいたい log2(len) <= 23 (len <= 50 * 100000)ぐらいです.

移動距離の上限lenが与えられたとします.
任意の頂点rを根として根付き木を考えます.
f:id:tatanaideyo:20150605204456p:plain
キツネたちを移動距離の上限lenを超えないように根を中心にお互いに連絡できるように集めます.
ここで、各キツネに対して移動することが出来る頂点を考えます.
上の図では次のようになります.
 ・キツネ0 = {0, 1, 2, 3, 4, 5}
 ・キツネ1 = {5, 6}
 ・キツネ2 = {0, 2, 5, 7}

次に、各キツネを根に向けて集めた時に上限lenのために移動することができない頂点を考えます.
上の図では次のようになります.それぞれの和集合をneed={0,2}とします.
 ・キツネ0 = {}
 ・キツネ1 = {0, 2}
 ・キツネ2 = {}
f:id:tatanaideyo:20150605204749p:plain
もし、すべてのキツネに対して移動することが出来ない頂点がなければみんな根に集まることによってお互いに連絡することが出来ます.
しかし、あるキツネに対して移動することが出来ない頂点があるならば他のキツネがその頂点に来なければいけません.
上の図の場合ではキツネ1は根に移動することができないので他のキツネが頂点0,2に来る必要があります.
もし、他のキツネも移動することが出来なければ移動距離の上限lenを満たしながら根を中心に集まることが出来ません.

この判定方法には二部グラフの最大マッチングを使用します.
次のようにして頂点sとtを加えてグラフを作成します.
 ・部グラフは木の頂点集合とキツネの集合
 ・頂点sからneedの頂点へ容量1の弧を張る
 ・キツネiが頂点vへ移動出来るときにvからiへ容量1の弧を張る
 ・各々のキツネからtへ容量1の弧を張る

図では容量1を省略して書いてます.
f:id:tatanaideyo:20150605211049p:plain
このグラフに最大流を流して最大マッチングの解を得ます(赤色の弧に対応).
f:id:tatanaideyo:20150605211334p:plain
選ばれた弧が意味するところは、キツネ0が頂点0に、キツネ2が頂点2に移動することに対応しており流量は2です.
これが、needの要素数と等しいとき、すべてのキツネが移動距離len以内で根rを中心に連絡可能な頂点に移動できたことになります.

ソースコード
typedef int Weight;

const int INF = 1e8;

struct Edge {
    int src, dst;
    Weight weight;
    int rev;
    Edge(int f, int t, Weight c, int rev = 0) :
        src(f), dst(t), weight(c), rev(rev) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void AddEdge(Graph &g, int s, int dst, Weight cap){
    g[s].push_back(Edge(s, dst, cap, g[dst].size()));
    g[dst].push_back(Edge(dst, s, 0, g[s].size()-1));
}

class Dinic {
private:
    void Bfs(const Graph &g, vector<int> &level, int s){
        level[s]=0;
        queue<int> que;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for (auto &e : g[v]) {
                if(e.weight > 0 && level[e.dst] < 0){
                    level[e.dst] = level[v] + 1;
                    que.push(e.dst);
                }
            }
        }
    }

    Weight Dfs(Graph &g, vector<int> &level, vector<int> &iter,
               int v, int t, Weight flow) {
        if(v == t)
            return flow;
        for (int &i = iter[v], N = g[v].size(); i < N; ++i) {
            Edge &e = g[v][i];

            if(e.weight > 0 && level[v] < level[e.dst]){
                Weight d = Dfs(g, level, iter, e.dst, t, min(flow, e.weight));
                if(d > 0){
                    e.weight -= d;
                    g[e.dst][e.rev].weight += d;
                    return d;
                }
            }
        }
        return 0;
    }

public:
    Weight DinicSolve(Graph &g, int s, int t){
        Weight flow = 0;

        while(true){
            vector<int> level(g.size(), -1);
            vector<int> iter(g.size(), 0);
            Bfs(g, level, s);

            if(level[t] < 0)
                break; // もう流せない
            Weight f = 0;
            while((f = Dfs(g, level, iter, s, t, INF)) > 0)
                flow += f;
        }

        return flow;
    }
};

class FoxMeeting {
    vector<int> tree[51];
    int d[51][51]; // treeの距離関数
    int n; // 頂点数
    vector<int> foxes;
    int nfox;

public:
	int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector <int> _foxes) {
        n = A.size() + 1;
        foxes = _foxes;
        nfox = foxes.size();
        for (auto &x : foxes)
            --x;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j)
                d[i][j] = INF;
            d[i][i] = 0;
        }

        // Make a tree
        for (int i = 0, size = A.size(); i < size; ++i) {
            tree[A[i] - 1].emplace_back(B[i] - 1);
            tree[B[i] - 1].emplace_back(A[i] - 1);
            d[A[i] - 1][B[i] - 1] = d[B[i] - 1][A[i] - 1] = L[i];
        }

        // Floyd Warshall
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (d[i][k] < INF && d[k][j] < INF)
                        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

        // 総移動距離に関する二分探索
       int lb = -1, ub = INF;
        while (ub - lb > 1) {
            int mid = (ub + lb) >> 1;
            if (Check(mid))
                ub = mid;
            else
                lb = mid;
        }

        return ub;
	}

    void MakeRootedTree(int now, int p, vector<int> &root) {
        root[now] = p;
        for (auto u : tree[now])
            if (u != p)
                MakeRootedTree(u, now, root);
    }

    bool Check(int len) {

        for (int r = 0; r < n; ++r) {
            // 根をrとして根付き木を作成
            vector<int> root(n);
            MakeRootedTree(r, -1, root);

            // foxが根へ向かう途中でlenより長い距離を必要とする
            // 頂点はtrueとする
            vector<bool> need(n, false);
            need[r] = true;
            for (auto v : foxes) {
                int res = len, p = v;
                while (p != r) {
                    res -= d[p][root[p]];
                    if (res < 0)
                        need[p] = true;
                    p = root[p];
                }
            }

            // 2部グラフのマッチング
            int s = n + nfox, t = s + 1;
            int n_need = 0;
            Graph g(t + 1);

            // sからneed[v]==trueを満たすvへ容量1の弧を張る
            for (int v = 0; v < n; ++v)
                if (need[v]) {
                    ++n_need;
                    AddEdge(g, s, v, 1);
                }
            // 頂点vからfoxまでの距離がlen以下なら容量1の弧を張る
            for (int v = 0; v < n; ++v)
                for (int i = 0; i < nfox; ++i)
                    if (d[v][foxes[i]] <= len)
                        AddEdge(g, v, i + n, 1);
            // foxからtへ容量1の弧を張る
            for (int i = 0; i < nfox; ++i)
                AddEdge(g, i + n, t, 1);

            Dinic dn;
            if (dn.DinicSolve(g, s, t) == n_need)
                return true;
        }

        return false;
    }
};