pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

【20点解法】CODE FESTIVAL 2015 エキシビション A - 高橋王国と青木王国

部分点解法です。部分点でも僕にとってはいい練習になったので記事にしました。

問題

最小カットによって同じ集合に含まれる可能性があるか、異なる集合に含まれる可能性があるかをそれぞれ判定する問題。

A: 高橋王国と青木王国 - CODE FESTIVAL 2015 エキシビション(オープンコンテスト) | AtCoder

解法

最小カットは最大流で求まる。容量1として辺を繋ぐ。
f:id:pekempey:20151115044136p:plain

流すと最小カットの候補が一つ求まる。この例だと最小カットは2。
f:id:pekempey:20151115044138p:plain

u,vが同じ集合に含まれるかを判定したければ、u,vを容量∞の辺で繋いで最小カットを求めればいい。このようにするとu,vは必ず同じ集合に含まれる。新しいグラフの最小カットが元のグラフの最小カットと等しければ、同じ集合に含むような最小カットが存在したということなのでYES、そうでなければNO。
f:id:pekempey:20151115044144p:plain

u,vが異なる集合に含まれるか判定するには次の2つを求めればいい。

  1. s,uを容量∞の辺で繋ぎ、t,vを容量∞の辺で繋いだグラフの最小カットC1
  2. s,vを容量∞の辺で繋ぎ、t,uを容量∞の辺で繋いだグラフの最小カットC2

s,uを容量∞の辺で繋げばuはs側に、t,vを容量∞の辺で繋げばvはt側に必ず属するようになる。C1,C2の少なくともどちらか一方が元のグラフの最小カットと等しければYES、そうでなければNO。

f:id:pekempey:20151115044151p:plain

f:id:pekempey:20151115044154p:plain

ソースコード

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;
 
struct MaxFlow {
    struct Edge { int to, cap, rev, isrev; };
    vector<int> dist, it;
    vector<vector<Edge>> G;
    MaxFlow(int n) : G(n), dist(n), it(n) {}
    void add(int u, int v, int c) {
        Edge a = {v, c, (int)G[v].size(), false};
        Edge b = {u, 0, (int)G[u].size(), true};
        G[u].push_back(a);
        G[v].push_back(b);
    }
    int calc(int s, int t) {
        int res = 0;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            while (int f = dfs(s, t, INT_MAX)) {
                res += f;
            }
        }
        return res;
    }
    bool bfs(int s, int t) {
        fill(dist.begin(), dist.end(), -1);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (Edge e : G[v]) {
                if (e.cap > 0 && dist[e.to] < 0) {
                    dist[e.to] = dist[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return dist[t] >= 0;
    }
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = it[v]; i < G[v].size(); i++) {
            Edge &e = G[v][i];
            if (e.cap > 0 && dist[v] < dist[e.to]) {
                if (int d = dfs(e.to, t, min(f, e.cap))) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
};
 
vector<int> G[5050];
 
int main() {
    int n, m;
    cin >> n >> m;
 
    MaxFlow mf(n);
    rep (i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        mf.add(a, b, 1);
    }
 
    MaxFlow mf2(mf);
    int src = 0, dst = n - 1;
    int mincut = mf2.calc(src, dst);
 
    int q;
    cin >> q;
 
    if (n > 100 || m > 1000 || q > 100) return 0;
 
    rep (i, q) {
        int c, d;
        scanf("%d %d", &c, &d);
        c--; d--;
        MaxFlow tmp(mf);
        tmp.add(c, d, 1e7);
        tmp.add(d, c, 1e7);
        int cut = tmp.calc(src, dst);
 
        MaxFlow tmp2(mf);
        tmp2.add(src, c, 1e7);
        tmp2.add(c, src, 1e7);
        tmp2.add(d, dst, 1e7);
        tmp2.add(dst, d, 1e7);
        int cut2 = tmp2.calc(src, dst);
 
        MaxFlow tmp3(mf);
        tmp3.add(src, d, 1e7);
        tmp3.add(d, src, 1e7);
        tmp3.add(c, dst, 1e7);
        tmp3.add(dst, c, 1e7);
        int cut3 = tmp3.calc(src, dst);
 
        string ans1, ans2;
        if (cut == mincut) {
            ans1 = "YES";
        } else {
            ans1 = "NO";
        }
 
        if (cut2 == mincut || cut3 == mincut) {
            ans2 = "YES";
        } else {
            ans2 = "NO";
        }
        cout << ans1 << " " << ans2 << endl;
    }
    return 0;
}

コメント

(s,u),(t,v)だけしかチェックしてなくて、(s,v),(t,u)もチェックしなきゃ駄目なのを見落としてた。