ABC285G Tatami

AC 的第一道上下界网络流。

题目传送门

用若干个 $1 \times 1$ 和 $1 \times 2$ 的瓷砖（可以旋转）不重叠地完全覆盖 $H \times W$ 的长方形网格。第 $i$ 行第 $j$ 列的网格有限制 $c_{i,j}$，含义如下：

• 1：该网格只能用 $1 \times 1$ 的瓷砖覆盖。
• 2：该网格只能用 $1 \times 2$ 的瓷砖覆盖。
• ?：无限制。

判断是否可行。

$H,W \le 300$

因为有 $1\times 1$ 的瓷砖比较自由，所以我们只需要考虑满足所有限制为 2 的格子就行了。

显然，按照 $i+j$ 的奇偶性可以将网格分成一个二分图。

对于两个相邻且可以用一个 $1\times 2$ 覆盖的格子（即都不是 1），连一条 $[0,1]$ 的边。

接着考虑每个点的流量限制：

• 对于 1，没有流量，不用连边。
• 对于 2，必须要用 $1\times 2$ 覆盖，向超级源点/汇点连一条 $[1,1]$ 的边。
• 对于 ?，可以用 $1\times 2$ 覆盖，也可以不用，向超级源点/汇点连一条 $[0,1]$ 的边。

然后用有源汇上下界可行流求解。

Code

int n, m;
string s[N];
char c[N][N];
int id(int x, int y) { return (x - 1) * m + y - 1; }
int S, T, S2, T2;
int in[N * N], out[N * N];
int cnt = -1;
int w[20 * N * N], to[20 * N * N], dep[20 * N * N];
vector<int>g[N * N];
void addedge2(int x, int y, int v) {
    // cout << x << ' ' << y << ' ' << v << endl;
    if (!v)return;
    ++cnt;
    w[cnt] = v, to[cnt] = y;
    g[x].pb(cnt);
    ++cnt;
    w[cnt] = 0, to[cnt] = x;
    g[y].pb(cnt);
}
void addedge(int x, int y, int l, int r) {
    // cout << x << ' ' << y << ' ' << l << ',' << r << endl;
    in[y] += l, out[x] += l;
    addedge2(x, y, r - l);
}
int sum = 0;
bool bfs() {
    init(dep, 0);
    dep[S2] = 1;
    queue<int> q;
    q.push(S2);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : g[x])
            if (w[y] && !dep[to[y]]) {
                dep[to[y]] = dep[x] + 1;
                q.push(to[y]);
            }
    }
    return (dep[T2] != 0);
}
int dfs(int x, int mn) {
    if (x == T2)
        return mn;
    int tmp = mn;
    for (int y : g[x]) {
        if (dep[to[y]] != dep[x] + 1 || !w[y])
            continue;
        int v = dfs(to[y], min(mn, w[y]));
        w[y] -= v;
        if (y % 2 == 0)
            w[y + 1] += v;
        else
            w[y - 1] += v;
        mn -= v;
        if (!mn)break;
    }
    if (tmp == mn)
        dep[x] = 0;
    return tmp - mn;
}
void solve() {
    cin >> n >> m;
    S = n * m, T = S + 1, S2 = T + 1, T2 = S2 + 1;
    addedge(T, S, 0, MAXN);
    rep(i, n)cin >> s[i];
    repp(i, n)repp(j, m)c[i][j] = s[i - 1][j - 1];
    repp(i, n)repp(j, m) {
        if ((i + j) % 2 == 0) {
            if (c[i][j] == '2')addedge(S, id(i, j), 1, 1);
            if (c[i][j] == '?')addedge(S, id(i, j), 0, 1);
        }
        else {
            if (c[i][j] == '2')addedge(id(i, j), T, 1, 1);
            if (c[i][j] == '?')addedge(id(i, j), T, 0, 1);
        }
    }
    repp(i, n)repp(j, m) {
        if (c[i][j] == '1')continue;
        rep(k, 2) {
            int x = i + k, y = j + 1 - k;
            if (c[x][y] == '2' || c[x][y] == '?') {
                if ((i + j) % 2 == 0)addedge(id(i, j), id(x, y), 0, 1);
                else addedge(id(x, y), id(i, j), 0, 1);
            }
        }
    }
    rep(i, T + 1) {
        if (in[i] > out[i])addedge2(S2, i, in[i] - out[i]), sum += in[i] - out[i];
        if (in[i] < out[i])addedge2(i, T2, out[i] - in[i]);
    }
    while (bfs())sum -= dfs(S2, MAXN);
    if (!sum)cout << "Yes";
    else cout << "No";
}