CF1592F2 Alice and Recoloring 2 题解

题意：

本题与 CF1592F1 的差异在于花费不同。

给定一个 $n$ 行 $m$ 列的目标矩阵，矩阵元素只有 W 或 B ，并且你有一个初始矩阵，元素全为 W 。

现在你可以矩阵实施以下操作：

使用一块钱，选定一个包含 $(1,1)$ 的子矩阵，把矩阵中的元素全部反转（ W 变 B ， B 变 W ）。

使用三块钱，选定一个包含 $(n,1)$ 的子矩阵，把矩阵中的元素全部反转。

使用四块钱，选定一个包含 $(1,m)$ 的子矩阵，把矩阵中的元素全部反转。

使用两块钱，选定一个包含 $(n,m)$ 的子矩阵，把矩阵中的元素全部反转。

现在需要你求出把初始矩阵变为目标矩阵最少需要几块钱。

输入格式：

第一行两个正整数 $n$ 和 $m (1 \le n,m\le 500)$ ，意义如上文所述。

接下来 $n$ 行，每行 $m$ 个字符 W 或 B 。意义如上文所述。

输出格式：

一行一个整数，表示把初始矩阵变为目标矩阵所需的最少钱数。

首先注意到 $(n,1)$ 的操作和 $(1,m)$ 的操作都是没意义的，都可以用 $(1,1)$ 的操作替代。

于是问题转化为，只有两种操作 $(1,1)$ 和 $(n,m)$ ，价格分别是 $1$ 和 $2$ 元。

对 $a_{i,j}$ 做一遍异或后缀和（ W 为 $1$ ），也就是 $a_{i,j} \gets a_{i, j} \oplus a_{i, j+1} \oplus a_{i+1, j} \oplus a_{i+1, j+1}$ 。

那么操作一就变成了取反 $a_{i,j}$，操作二变成了取反 $a_{i,j},\,a_{i,m},\,a_{n,j},\,a_{n,m}$ 。（要是做前缀和就是反过来）

现在需要将 $a_{i,j}$ 全部消成 $0$ 。注意到对于同一行的操作二 $(x,c_1)$ 和 $(x,c_2)$ ，花费了 $4$ 元却只改了 $4$ 个点。

那么同一行或同一列最多执行一次操作二，这使得我们好奇操作二在什么时候会使用。

注意到当 $a_{i,j} + a_{i,m} + a_{n,j} + a_{n,m} \le 2$ 时，操作二显然没必要使用。

于是操作二只会在 $a_{i,j}+a_{n,j}+a_{i,m} + a_{n,m}=3$ 时使用，而当 $a_{n,m}=1$ 时使用操作二无法正确的翻转

因此实际上只有 $a_{i,j}+a_{n,j}+a_{i,m}=3$ 时才会使用操作二。

由于同一行或同一列最多执行一次，那么对于某个 $i$ ，只能有一个 $j$ 和它配对，$j$ 同理。

考虑建立二分图，对于任意满足使用操作二的前置条件的 $(i,j)$ ，我们将左侧的 $i$ 与右侧的 $j$ 连边。

记这张图的二分图最大匹配数为 $k$ ，答案就是剩下的 $1$ 的个数减去 $k$ 。注意 $a_{n,m}$ 被翻转了 $k$ 次。

因为 Dinic 跑二分图最大匹配的复杂是 $\mathcal{O}\left(|E|\sqrt{|V|}\right)$ ，本题 $|V|=\mathcal{O}(n)$ ，$|E|=\mathcal{O}(nm)$

所以时间复杂度为 $\mathcal{O}(n^{1.5}m)$ ，

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(555))

char s[N][N];
int n, m, tot, S, T, pos = 1, a[N][N], head[N * 2], now[N * 2], dep[N * 2];
struct Edge { int u, v, w, next; } e[N * N * 2];
void addEdge(int u, int v, int w) { e[++pos] = {u, v, w, head[u]}; head[u] = pos; }
void addE(int u, int v) { addEdge(u, v, 1); addEdge(v, u, 0); }
bool bfs()
{
    static queue<int> q; while(!q.empty()) q.pop();
    rep(i, 1, tot) dep[i] = INF;
    q.push(S); dep[S] = 1; now[S] = head[S];
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if(e[i].w > 0 && dep[v] == INF)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v]; q.push(v);
            }
        }
    }
    return dep[T] != INF;
}
int dfs(int u, int in)
{
    if(u == T) return in;
    int out = 0;
    for(int i = now[u]; i && in; i = e[i].next)
    {
        int v = e[i].v; now[u] = i;
        if(e[i].w > 0 && dep[v] == dep[u] + 1)
        {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res; e[i ^ 1].w += res;
            in -= res; out += res;
        }
    }
    if(!out) dep[u] = INF;
    return out;
}
int Dinic()
{
    int res = 0;
    while(bfs()) res += dfs(S, INF);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    S = n + m + 1, T = n + m + 2; tot = n + m + 2;
    rep(i, 1, n) cin >> (s[i] + 1);
    rep(i, 1, n) rep(j, 1, m) {
        a[i][j] = (s[i][j] == 'B') ^ (s[i][j + 1] == 'B')
            ^ (s[i + 1][j] == 'B') ^ (s[i + 1][j + 1] == 'B');
    }
    rep(i, 1, n - 1) rep(j, 1, m - 1)
        if(a[i][j] && a[n][j] && a[i][m]) addE(i, j + n);
    rep(i, 1, n - 1) addE(S, i);
    rep(j, 1, m - 1) addE(j + n, T);
    int k = Dinic(), res = 0;
    a[n][m] ^= (k & 1);
    rep(i, 1, n) rep(j, 1, m) res += a[i][j];
    res -= k; cout << res << '\n';
    return 0;
}