ICPC 本番に正解チームの現れなかった難問！

問題へのリンク

問題概要

$H \times W$ サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。

このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求めよ。存在しない場合にはそのことを報告せよ。

制約

$1 \le H, W \le 400$

考えたこと：マトロイド交差になる

グリッドグラフと言われたら、まずは頂点を市松模様に塗って、二部グラフに帰着させるものだと相場は決まっている。このとき、各頂点の色を白色・黒色としたとき、求めるグラフは次の条件を満たすものとなる。

条件 A：全域木である
条件 B：葉が白色のみであるか、葉が黒色のみである

ここで、与えられたグラフから「全域木にするために削除する辺の集合」に着目すると、上記の条件はマトロイド交差になっている。なお、これ以降、頂点 $v$ の次数を $d(v)$ と書くことにする。

条件 A を満たす削除辺集合：補グラフ的マトロイド
条件 B を満たす削除辺集合：各白色頂点 $v$ について、 $v$ に接続する辺のうち、選べる辺が $d(v) - 2$ 本以下であるとする分割マトロイド（葉が黒色のみである場合）

しかしながら、一般的なマトロイド交差のアルゴリズムを用いても TLE になるようだ。この問題に特徴的な構造を活用する必要があるらしい。

気づいたこと：左右の頂点の個数が一致してはいけない

どのようなグラフだと、条件を満たす全域木が存在しないのかについて考えていくことにした。まず、次のことがわかった。

二部グラフのうち、各側の頂点の集合をそれぞれ $P, Q$ とする。

$|P| \le |Q|$ であるとき、 $P$ 側の頂点のみに葉があるような全域森は存在しない (全域木が存在しないことより強い主張)。

とくに、 $|P| = |Q|$ であるとき、 $P, Q$ のいずれかの側にのみ葉があるような全域森は存在しない。

簡単に証明しておく。全域森の辺の本数は $|P| + |Q| - 1$ 以下であることから、

$\displaystyle \sum_{v \in Q} d(v) \le |P| + |Q| - 1$

となる。ここで、 $P$ 側の頂点のみに葉があるような全域森が存在すると仮定すると $d(v) \ge 2$ ( $v \in Q$ ) であるから、

$|P| + |Q| - 1 \ge \displaystyle \sum_{v \in T} d(v) \ge 2|Q|$
⇔ $|P| - 1 \ge |Q|$

となる。これは、 $|P| \le | Q|$ に矛盾する。

ここまでの考察は悪くなかったが、ここから先の考察は上手く進められなかったので、解説を少しずつ読んでみた。

二部グラフの最大マッチングを考える

解説を読むと、二部グラフの最大マッチングを考えるとあった（実のところ、未だに、なぜ最大マッチングを考えたくなるのかはよくわかっていない）。

まず、次のことが言えるようだ。

二部グラフの各側の頂点集合を $P, Q$ とおいて、 $|P| \lt |Q$ ] とする。

二部グラフの最大マッチングのサイズが $|P|$ 未満であるとき、条件を満たす全域木は存在しない。

この証明はそれほど難しくはない。もし条件を満たす全域木が存在するならば、葉はすべて $|Q|$ 側である。このとき、

「葉を 1 つ選んで、それに接続する辺をマッチング辺とする」

という貪欲法によって、サイズが $|P|$ のマッチングが作れることが分かる。

到達可能頂点を考える

ここからが、yy さん作問の真骨頂！！　本当にすごい。

頂点集合 $T$ に含まれる頂点のうち、マッチングの端点でない頂点たちを始点として、次のように各辺を向き付けした有向グラフ上で DFS をする。

マッチング辺については、 $P$ 側頂点から $Q$ 側頂点へと向きをつける
それ以外の辺については、 $Q$ 側頂点から $P$ 側頂点へと向きをつける

このとき、次のことが言えるのだ！！

すべての頂点に到達可能であるとき：DFS 森 (をいくつかの辺で繋いだもの) は、 $Q$ 側にのみ葉がある全域木となる
到達不可能な頂点があるとき：条件を満たす全域木は存在しない

すべての頂点に到達可能であるとき

すべての頂点に到達可能である場合に、DFS 森 (をいくつかの辺で繋いだもの) が $Q$ 側にのみ葉がある全域木となることは、比較的容易にわかる。

$P$ 側の頂点はすべてマッチングの端点であるため、 $P$ 側が DFS 木の終端になることはありえない。

なぜならば、マッチング辺 $e = (u, v)$ ( $u \in P, v \in Q$ ) に対して、DFS の途中で $u$ を探索したときに、 $v$ が探索済みであることはありえない。 $v$ は、マッチング辺 $e = (u, v)$ を通ることによってのみ到達可能な頂点であるためだ。

到達不可能な頂点があるとき

この場合に、条件を満たす全域木が存在しないことの証明の方が少し難しい。

到達可能頂点の集合を $S$ 、到達不可能頂点の集合を $T$ としよう。このとき、 $S$ 側の頂点 $u$ と $T$ 側の頂点 $v$ とを結ぶ辺 $e$ があるとき、この辺は次の 4 パターンのいずれかになるはずである。

パターン A： $e$ はマッチング辺であり、 $u \in P, v \in Q$ である
パターン B： $e$ はマッチング辺であり、 $u \in Q, v \in P$ である
パターン C： $e$ はマッチング辺ではなく、 $u \in P, v \in Q$ である
パターン D： $e$ はマッチング辺ではなく、 $u \in Q, v \in P$ である

これらのうち、パターン A, B, D はあり得ないことが言える。

パターン A, D がありうると仮定すると、 $u$ が到達可能であって、さらに $u$ から辺 $e$ をたどって $v$ にも到達可能であって矛盾
パターン B がありうると仮定すると、 $v$ が到達可能であるためには、 $u$ が到達可能でなければならないので、矛盾

よって、パターン C しかないため、到達不可能な頂点の集合 $T$ は下の図のように、かならず「 $P$ 側の頂点の個数 = $Q$ 側の頂点の個数」を満たす形となる。

したがって、 $T$ の内部で条件を満たす全域森を作ることができず、グラフ全体でも条件を満たす全域森を作ることができないことがわかった。

コード

以上の解法を実装する。二部マッチングを求める部分で Dinic 法を用いると、計算量は $O((HW)^{1.5})$ と評価できる。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

// Union-Find
struct UnionFind {
    // core member
    vector<int> par, nex;

    // constructor
    UnionFind() { }
    UnionFind(int N) : par(N, -1), nex(N) {
        init(N);
    }
    void init(int N) {
        par.assign(N, -1);
        nex.resize(N);
        for (int i = 0; i < N; ++i) nex[i] = i;
    }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        swap(nex[x], nex[y]);
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // get group
    vector<int> group(int x) {
        vector<int> res({x});
        while (nex[res.back()] != x) res.push_back(nex[res.back()]);
        return res;
    }
    vector<vector<int>> groups() {
        vector<vector<int>> member(par.size());
        for (int v = 0; v < (int)par.size(); ++v) {
            member[root(v)].push_back(v);
        }
        vector<vector<int>> res;
        for (int v = 0; v < (int)par.size(); ++v) {
            if (!member[v].empty()) res.push_back(member[v]);
        }
        return res;
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        const vector<vector<int>> &gs = uf.groups();
        for (const vector<int> &g : gs) {
            s << "group: ";
            for (int v : g) s << v << " ";
            s << endl;
        }
        return s;
    }
};

// edge class (for network-flow)
template<class FLOWTYPE> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    
    // constructor
    FlowEdge(int r, int f, int t, FLOWTYPE c)
    : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& E) {
        return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOWTYPE>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.assign(n, FlowEdge<FLOWTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOWTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowEdge<FLOWTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOWTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOWTYPE>> get_edges() const {
        vector<FlowEdge<FLOWTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) {
        FlowEdge<FLOWTYPE> &re = get_rev_edge(e);
        e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow;
        re.cap = new_flow;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// Dinic
template<class FLOWTYPE> FLOWTYPE Dinic
 (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow)
{
    FLOWTYPE current_flow = 0;
    vector<int> level((int)G.size(), -1), iter((int)G.size(), 0);
    
    // Dinic BFS
    auto bfs = [&]() -> void {
        level.assign((int)G.size(), -1);
        level[s] = 0;
        queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const FlowEdge<FLOWTYPE> &e : G[v]) {
                if (level[e.to] < 0 && e.cap > 0) {
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        }
    };
    
    // Dinic DFS
    auto dfs = [&](auto self, int v, FLOWTYPE up_flow) {
        if (v == t) return up_flow;
        FLOWTYPE res_flow = 0;
        for (int &i = iter[v]; i < (int)G[v].size(); ++i) {
            FlowEdge<FLOWTYPE> &e = G[v][i], &re = G.get_rev_edge(e);
            if (level[v] >= level[e.to] || e.cap == 0) continue;
            FLOWTYPE flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        bfs();
        if (level[t] < 0) break;
        iter.assign((int)iter.size(), 0);
        while (current_flow < limit_flow) {
            FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow);
            if (!flow) break;
            current_flow += flow;
        }
    }
    return current_flow;
};

template<class FLOWTYPE> FLOWTYPE Dinic(FlowGraph<FLOWTYPE> &G, int s, int t) {
    return Dinic(G, s, t, numeric_limits<FLOWTYPE>::max());
}

// 4-neighbor
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};


int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> field(H * 2 + 1), res(H * 2 + 1, string(W * 2 + 1, '#'));
    vector<bool> seen(H * W, true);
    int even = 0, odd = 0;
    for (int i = 0; i < H * 2 + 1; i++) {
        cin >> field[i];
        if (i % 2 == 1) {
            int x = i / 2;
            for (int j = 1; j < W * 2 + 1; j += 2) {
                int y = j / 2;
                if (field[i][j] == '.') {
                    res[i][j] = '.';
                    seen[x * W + y] = false;
                    if ((x + y) % 2 == 0) even++;
                    else odd++;
                }
            }
        }
    }
    if (even == odd) {
        cout << "No" << endl;
        return 0;
    }

    // 二部マッチング
    FlowGraph<int> G(H * W + 2);
    int s = H * W, t = H * W + 1;
    set<int> leftnode, rightnode;
    vector<pint> edges;
    for (int x = 0; x < H; x++) {
        for (int y = 0; y < W; y++) {
            int i = x * 2 + 1, j = y * 2 + 1, v = x * W + y;
            if (seen[v]) continue;
            bool iseven = ((x + y) % 2 == 0);
            if (even > odd && iseven) {
                G.add_edge(v, t, 1);
                rightnode.insert(v);
                continue;
            }
            if (even < odd && !iseven) {
                G.add_edge(v, t, 1);
                rightnode.insert(v);
                continue;
            };
            G.add_edge(s, v, 1);
            leftnode.insert(v);
            for (int d = 0; d < 4; d++) {
                int x2 = x + dx[d], y2 = y + dy[d], i2 = i + dx[d], j2 = j + dy[d];
                if (x2 < 0 || x2 >= H || y2 < 0 || y2 >= W) continue;
                int left = x * W + y, right = x2 * W + y2;
                if (field[i2][j2] == '.') {
                    edges.emplace_back(left, right);
                    G.add_edge(left, right, 1);
                }
            }
        }
    }
    int maxflow = Dinic(G, s, t);
    if (maxflow < leftnode.size()) {
        cout << "No" << endl;
        return 0;
    }

    // マッチングに使われていない頂点から DFS
    vector<int> start, matched(H * W, -1);
    for (auto v : leftnode) {
        for (auto e : G[v]) {
            if (e.to != s && e.flow == 1) {
                matched[e.from] = e.to;
                matched[e.to] = e.from;
            }
        }
    }
    for (auto v : rightnode) {
        if (matched[v] == -1) start.emplace_back(v);
    }
    UnionFind uf(H * W);
    vector<pint> res_edges;
    auto rec = [&](auto rec, int v) -> void {
        seen[v] = true;
        if (leftnode.count(v)) {
            int to = matched[v];
            if (to == -1 || seen[to]) return;
            res_edges.emplace_back(v, to);
            uf.merge(v, to);
            rec(rec, to);
        }
        if (rightnode.count(v)) {
            for (auto e : G[v]) {
                if (e.to == matched[v] || e.to == t || seen[e.to]) continue;
                res_edges.emplace_back(v, e.to);
                uf.merge(v, e.to);
                rec(rec, e.to);
            }
        }
    };
    for (auto v : start) {
        rec(rec, v);
    }

    // もし行き渡っていない頂点があったら No
    for (int v = 0; v < H * W; v++) {
        if (!seen[v]) {
            cout << "No" << endl;
            return 0;
        }
    }

    // 連結にする
    for (auto [u, v] : edges) {
        if (!uf.same(u, v)) {
            res_edges.emplace_back(u, v);
            uf.merge(u, v);
        }
    }

    // 答えを作る
    for (auto [u, v] : res_edges) {
        int ui = (u / W) * 2 + 1, uj = (u % W) * 2 + 1;
        int vi = (v / W) * 2 + 1, vj = (v % W) * 2 + 1;
        int mi = (ui + vi) / 2, mj = (uj + vj) / 2;
        res[mi][mj] = '.';
    }
    cout << "Yes" << endl;
    for (auto str : res) cout << str << endl;
}