ABC472G

Asdfre

2026-08-22 22:25:53

发布于：广东

11阅读

0回复

0点赞

前言：刚学了网络流 G 就有了，大涨！

根据题意，我们可以提取出核心的两个对立方：'+' 和 '-'，一个 '+' 消失代价为 $1$ ，一个 '-' 消失收益为 $1$ 。

考虑一次操作影响：是强制地将左，右，下非 '#' 修改为 '#'，这时候就出现了依赖关系：选择 $u$ 就必须选择 $v$ ，可以在 $u$ 和 $v$ 中连边，这样就形成了一个图，我们要在满足依赖关系的条件下，选择一个子集，是的收益与代价的差最大。显然是一个最小割。

建立一个源点 $S$ 连向所有收益点，汇点 $T$ 连向所有代价点，容量为 $1$ 。

对于每个非 '#' 的格子，与左，右，下非 '#' 的点连一条容量为 $+\infty$ 。

这是为了满足强制关系，不让这两个点分到不同的集合（因为如果分到不同集合，显然不可能作为最小割）。

最后处理一下初始值跑一个 Dinic 即可。

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
    using ll = long long;
    using ull = unsigned long long;
    using i128 = __int128;
    using lb = long double;
    void init() {
        //		freopen("1.in","r",stdin);
        //		freopen("my.out","w",stdout);
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }
    constexpr int N = 35, M = 1e5 + 5, inf = 2e9;
    int n, m, s, t;
    string a[N];
    int base, tot;
    int get_id(int i, int j) { return (i - 1) * m + j; }
    struct Node {
        int to, nxt, val;
    } e[M];
    int head[N * N], cnt;
    void add(int u, int v, int val) {
        e[cnt] = {v, head[u], val};
        head[u] = cnt++;
        e[cnt] = {u, head[v], 0};
        head[v] = cnt++;
    }
    int dep[N * N], cur[N * N];
    bool bfs() {
        memset(dep, -1, sizeof dep);
        queue<int> q;
        dep[s] = 0, q.push(s), cur[s] = head[s];
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int i = head[u]; ~i; i = e[i].nxt) {
                int v = e[i].to;
                if (dep[v] == -1 && e[i].val) {
                    dep[v] = dep[u] + 1;
                    cur[v] = head[v];
                    if (v == t)
                        return true;
                    q.push(v);
                }
            }
        }
        return false;
    }
    int find(int u, int lim) {
        if (u == t)
            return lim;
        int flow = 0;
        for (int i = cur[u]; ~i && lim > flow; i = e[i].nxt) {
            int v = e[i].to;
            cur[u] = i;
            if (dep[v] == dep[u] + 1 && e[i].val) {
                int tmp = find(v, min(e[i].val, lim - flow));
                if (!tmp)
                    dep[v] = -1;
                e[i].val -= tmp, e[i ^ 1].val += tmp, flow += tmp;
            }
        }
        return flow;
    }
    int Dinic() {
        int Flow = 0;
        while (bfs()) {
            while (int flow = find(s, inf)) {
                Flow += flow;
            }
        }
        return Flow;
    }
    void Main() {
        memset(head, -1, sizeof head);
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i] = '&' + a[i];
            for (int j = 1; j <= m; ++j) {
                if (a[i][j] == '+') {
                    ++base;
                } else if (a[i][j] == '-') {
                    --base, ++tot;
                }
            }
        }
        s = 0, t = n * m + 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (a[i][j] == '#')
                    continue;
                int u = get_id(i, j);
                if (a[i][j] == '-')
                    add(s, u, 1);
                else if (a[i][j] == '+')
                    add(u, t, 1);
                if (j > 1 && a[i][j - 1] != '#')
                    add(u, get_id(i, j - 1), inf);
                if (j < m && a[i][j + 1] != '#')
                    add(u, get_id(i, j + 1), inf);
                if (i < n && a[i + 1][j] != '#')
                    add(u, get_id(i + 1, j), inf);
            }
        }
        cout << tot - Dinic() + base;
    }
} // namespace CZW
int main() {
    CZW::init();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        CZW::Main();
    return 0;
}