CF1368H1 Breadboard Capacity (easy version) (3300🥵)

· · 题解

https://www.luogu.com.cn/problem/CF1368H1

我觉得这题很难啊。*3300 没错。

首先发现这个问题其实是类似一个匹配问题，考虑连成一个类似网格图的形状，其中每条边的容量为 1，直接让 S 到所有红色点连边，所有蓝色点到 T 连边，跑最大流即可得到答案：

但是这个数据范围高达 10^5，直接流肯定是不行的，H2 还要带修那肯定要另想办法。

首先我们最大流转最小割，于是问题可以转化为对上图中的所有黑色点染成红蓝两色，代表和 S 连通还是和 T 连通，这样割的大小就是双色边（一边是红一边是蓝）的数量。

发现这样还是做不了，我们考虑发现一些基本的性质。

考虑对偶图，对于每一条双色边，都把相邻的两个面连一条边，接下来有三个观察：

容易发现这种情况一定是一个同色连通块外边被一个颜色不同的同色连通块包住，这样我们一定可以调整所有在网格图内部的蓝色点的颜色成红色消掉这个环。

这种情况我们可以把所有相关的红色全部调整为蓝色，容易证明答案一定不会变劣（一条端点为红色和蓝色的一条路径一定有一条双色边，类似区间根定理）：

下面这种情况：

同理，可以把内部的红色点都调整成蓝色，答案同样不会变劣。

可以将上面的两个凸起对应的红色点调整为蓝色，答案也同样不会变劣：

有了这三个观察，可以发现所有同色极大连通块都一定连了边界（否则会出现环），由于有第二个观察，所以不会有连了一个边界但是不连对面边界的情况，因为这样一定是被异色点包住了，一定会出现第二个观察的不优情况。也就是说对偶图上的路径一定会连到边界面。又因为第三个观察，可以发现这些路径一定是直的，所以只会存在连接对面边界的从上到下或从左到右的整条的路径。

容易发现不可能同时存在从上到下和从左到右的路径，因为这样就连通了相邻边界。

于是一定有一种路径是没有的，根据定义发现，最终的染色策略一定形如 整行染相同颜色 或 整列染相同颜色，容易进行 2 次 DP 解决，时间复杂度 O(n + m)。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace PTqwq {

int readqwq() {
    int x = 0;
    bool f = false;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) f |= (c == '-');
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c - '0');
    if (f) {
        x = -x;
    }
    return x;
}

ll readllqwq() {
    ll x = 0;
    bool f = false;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) f |= (c == '-');
    for (; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c - '0');
    if (f) {
        x = -x;
    }
    return x;
}

const int N = 1e5 + 10;
const ll infLL = 1e18;

void chkmin(ll& x, ll y) {
    if (x > y) {
        x = y;
    }
}

int n, m, q, vala[N], valb[N], valc[N], vald[N];
ll f[N][2], g[N][2];
char a[N], b[N], c[N], d[N];

void Solve() {
    n = readqwq(); m = readqwq(); q = readqwq();
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    scanf("%s", c + 1);
    scanf("%s", d + 1);
    for (int i = 1; i <= n; ++ i) {
        vala[i] = (a[i] == 'R' ? 1 : 0);
        valb[i] = (b[i] == 'R' ? 1 : 0);
    }
    for (int i = 1; i <= m; ++ i) {
        valc[i] = (c[i] == 'R' ? 1 : 0);
        vald[i] = (d[i] == 'R' ? 1 : 0);
    }
    for (int i = 0; i <= n; ++ i) {
        f[i][0] = infLL; f[i][1] = infLL;
    }
    for (int i = 0; i <= m; ++ i) {
        g[i][0] = infLL; g[i][1] = infLL;
    }

    ll ans = infLL;

    f[1][0] = 0; f[1][1] = 0;
    for (int i = 1; i <= m; ++ i) f[1][valc[i]] ++;
    f[1][vala[1]] ++; f[1][valb[1]] ++;
    for (int i = 2; i <= n; ++ i) {
        chkmin(f[i][0], f[i - 1][0]);
        chkmin(f[i][0], f[i - 1][1] + (1ll * m));
        chkmin(f[i][1], f[i - 1][1]);
        chkmin(f[i][1], f[i - 1][0] + (1ll * m));
        f[i][vala[i]] ++; f[i][valb[i]] ++;
    }
    for (int i = 1; i <= m; ++ i) f[n][vald[i]] ++;
    chkmin(ans, f[n][0]); chkmin(ans, f[n][1]);

    g[1][0] = 0; g[1][1] = 0;
    for (int i = 1; i <= n; ++ i) g[1][vala[i]] ++;
    g[1][valc[1]] ++; g[1][vald[1]] ++;
    for (int i = 2; i <= m; ++ i) {
        chkmin(g[i][0], g[i - 1][0]);
        chkmin(g[i][0], g[i - 1][1] + (1ll * n));
        chkmin(g[i][1], g[i - 1][1]);
        chkmin(g[i][1], g[i - 1][0] + (1ll * n));
        g[i][valc[i]] ++; g[i][vald[i]] ++;
    }
    for (int i = 1; i <= n; ++ i) g[m][valb[i]] ++;
    chkmin(ans, g[m][0]); chkmin(ans, g[m][1]);

    printf("%lld\n", ans);
}

}

int main() {
    PTqwq::Solve();

    return 0;
}