TCO15 Round 2A med:FoxMeeting

言われてみるとなんで気づかなかったって言う奴なんだよなぁ…
なんとなくこれ↓に発想が似てる気がする。mayokoex.hatenablog.com

問題

TopCoder Statistics - Problem Statement

解法

基本的には狐の最大の移動量xについて二分探索して答えを求める。ということで
ok(x):移動量をx以下に抑える方法が存在するならtrueを返す関数
を作ることが目標になる。

ok(x)ではa=0〜n-1について「各頂点aに集合できるか」を調べます。
foxのいる各頂点からaにできるだけ近づこうとしますが,どうしてもaまでたどり着くことができない狐がいるかもしれません。
このとき,この狐がもともといた頂点からaまでの道筋のうち,どこまでを「別の狐を持ってくることによって連結させるか」ということを考えます。例を挙げると,

fox->...->b->c->d->a

というように狐がもともといた頂点foxと目標となる頂点aがつながっていて,foxからはbまでしか距離xでは辿りつけないとすると,c, d, aには他の狐がいてくれないと連結できないので困ります。

ということで,各狐について「その狐にとって,他の狐がいてくれないと困る頂点」を列挙することが出来ます。aに集合することができるためには,この「困る頂点」すべてにうまいこと狐が集合してくれることが必要十分条件です。

これは狐と「困る頂点」の二部マッチング問題と解釈することができるので,これを解いてやりましょう。ある狐からある「困る頂点」に距離xで移動することができる時,その狐と頂点を辺で結ぶようなグラフで最大費用流を流せば良いですね。

// Dinic法:最小カット,最大フローで使う
// 使い方: Dinic* dinic = new Dinic(V)で初期化(Vは頂点数)
// dinic->add_edgeまたはdinic->add_edge_bothで点をつなげてdinic->max_flowで最大フローを求める
#define NG -1
#define SZ(a) ((int)((a).size()))
class Dinic
{
public:
    Dinic(int input_maxv) : maxv(input_maxv)
    {
        G.resize(input_maxv);
        level.resize(input_maxv);
        iter.resize(input_maxv);
    }

    void add_edge_both(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,cap,rev_from));
    }

    void add_edge(int from, int to, int cap)
    {
        const int rev_from  = SZ(G[from]);
        const int rev_to    = SZ(G[to]);
        G[from].push_back(edge(to,cap,rev_to));
        G[to].push_back(edge(from,0,rev_from));
    }

    int max_flow(int s, int t)
    {
        int flow = 0;
        for(;;)
        {
            bfs(s);
            if(level[t]<0) break;
            fill(iter.begin(),iter.end(),0);
            int f;
            while( (f=dfs(s,t,DINIC_INF))>0)
            {
                flow += f;
            }
        }

        return flow;
    }

    vector <bool> get_nodes_in_group(int s)
    {
        vector <bool> ret(maxv);

        queue<int> que;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            ret[v]=true;

            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && !ret[e.to])
                {
                    que.push(e.to);
                }
            }
        }
        return ret;
    }

    void disp()
    {
        for (int v = 0; v < maxv; v++)
        {
            printf("%d:",v);
            for(int i=0;i<SZ(G[v]);i++)
            {
                if(G[v][i].init_cap>0)
                {
                    printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
                }
            }
            printf("\n");
        }
    }

private:
    void bfs(int s)
    {
        fill(level.begin(),level.end(),NG);
        queue<int> que;
        level[s]=0;
        que.push(s);
        while(!que.empty())
        {
            int v = que.front();
            que.pop();
            for(int i=0;i<SZ(G[v]);i++)
            {
                edge &e = G[v][i];
                if(e.cap>0 && level[e.to]<0)
                {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f)
    {
        if(v==t) return f;
        for (int &i=iter[v];i<SZ(G[v]);i++)
        {
            edge& e = G[v][i];
            if(e.cap>0 && level[v]<level[e.to])
            {
                int d = dfs(e.to, t, min(f, e.cap));
                if(d>0)
                {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    static const int DINIC_INF = INT_MAX;

    struct edge
    {
        edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
        int to;
        int cap;
        int rev;
        int init_cap;
    };

    int maxv;
    vector < vector <edge> > G;
    vector < int > level;
    vector < int > iter;

};

const int MAXN = 55;
const int INF = 1e9;
vector<int> A, B, L, foxes;
int d[MAXN][MAXN];
int n, m;
bool can[MAXN][MAXN];

bool ok(int med) {
    memset(can, 0, sizeof(can));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (d[i][j] <= med) can[i][j] = true;
        }
    }
    for (int a = 0; a < n; a++) {
        // a:集合してくる頂点
        // should:集まってこないといけない頂点の集合
        vector<int> should;
        for (int i = 0; i < m; i++) {
            int fox = foxes[i];
            for (int j = 0; j < n; j++) {
                if (!can[fox][j] && d[fox][j] + d[j][a] == d[fox][a]) should.push_back(j);
            }
        }
        sort(should.begin(), should.end());
        should.erase(unique(should.begin(), should.end()), should.end());
        int p = should.size();
        if (p == 0) return true;
        int s = p+m+1, t = s+1, V = t+1;
        Dinic* dinic = new Dinic(V);
        for (int i = 0; i < m; i++) {
            dinic->add_edge(s, i, 1);
        }
        for (int i = 0; i < p; i++) {
            dinic->add_edge(i+m, t, 1);
        }
        for (int i = 0; i < m; i++) {
            int fox = foxes[i];
            for (int j = 0; j < p; j++) {
                if (can[fox][should[j]]) dinic->add_edge(i, j+m, 1);
            }
        }
        int ans = (dinic->max_flow(s, t));
        if (ans == p) return true;
    }
    return false;
}

class FoxMeeting {
public:
    int maxDistance(vector <int> AA, vector <int> BB, vector <int> LL, vector <int> Foxes) {
        A = AA; B = BB; L = LL; foxes = Foxes;
        n = A.size()+1;
        m = foxes.size();
        for (int i = 0; i < n-1; i++) {
            A[i]--; B[i]--;
        }
        for (int i = 0; i < m; i++) {
            foxes[i]--;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = INF;
            }
            d[i][i] = 0;
        }
        for (int i = 0; i < n-1; i++) {
            d[A[i]][B[i]] = d[B[i]][A[i]] = L[i];
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        int low = -1, high = 100000*MAXN;
        while (high - low > 1) {
            int med = (high+low) / 2;
            if (ok(med)) high = med;
            else low = med;
        }
        return high;
    }
};