ABC472G
2026-08-22 22:25:53
发布于：广东
2阅读
0回复
0点赞
前言：刚学了网络流 G 就有了，大涨！
根据题意，我们可以提取出核心的两个对立方：'+' 和 '-'，一个 '+' 消失代价为 ，一个 '-' 消失收益为 。
考虑一次操作影响：是强制地将左，右，下非 '#' 修改为 '#'，这时候就出现了依赖关系：选择 就必须选择 ，可以在 和 中连边，这样就形成了一个图，我们要在满足依赖关系的条件下，选择一个子集，是的收益与代价的差最大。显然是一个最小割。
建立一个源点 连向所有收益点，汇点 连向所有代价点，容量为 。
对于每个非 '#' 的格子，与左，右，下非 '#' 的点连一条容量为 。
这是为了满足强制关系，不让这两个点分到不同的集合（因为如果分到不同集合，显然不可能作为最小割）。
最后处理一下初始值跑一个 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;
}
有帮助，赞一个