感觉是一种很新的建图方式。
首先肯定是最小割没跑了。尝试描述损失。
也不难发现要连 \(S \to (i, j)\),容量 \(a_{i, j}\),这样描述出了每个点选与不选的状态。
考虑如何描述 X。考虑连边 \((i, j) \to (i + 1, j - 1), (i, j) \to (i + 1, j + 1), (n, 1) \to T, (n, m) \to T\),容量均为 \(C\)。表示对于一条斜线,在它的终止位置的连向下一个点的边会被割断,否则 \(S\) 能到达这些点跟下一个斜线的点,那跟选终止位置下一个点的效果相同,还不如不割,即选择它。
复杂度好像是错的,但是可过。
code
// Problem: G - X
// Contest: AtCoder - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)
// URL: https://atcoder.jp/contests/abc225/tasks/abc225_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const int maxm = 1000100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m, K, a[maxn][maxn], head[maxm], len = 1, ntot, S, T, id[maxn][maxn];
struct edge {
ll to, next, cap, flow;
} edges[maxm];
inline void add_edge(ll u, ll v, ll c, ll f) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
head[u] = len;
}
struct Dinic {
ll d[maxm], cur[maxm];
bool vis[maxm];
inline void add(ll u, ll v, ll c) {
add_edge(u, v, c, 0);
add_edge(v, u, 0, 0);
}
inline bool bfs() {
for (int i = 1; i <= ntot; ++i) {
d[i] = -1;
vis[i] = 0;
}
queue<int> q;
q.push(S);
vis[S] = 1;
d[S] = 0;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
ll dfs(ll u, ll a) {
if (u == T || !a) {
return a;
}
ll flow = 0, f;
for (ll &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline ll solve() {
ll flow = 0;
while (bfs()) {
for (int i = 1; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
S = ++ntot;
T = ++ntot;
ll s = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%lld", &a[i][j]);
id[i][j] = ++ntot;
s += a[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
solver.add(S, id[i][j], a[i][j]);
if (i < n && j > 1) {
solver.add(id[i][j], id[i + 1][j - 1], K);
} else {
solver.add(id[i][j], T, K);
}
if (i < n && j < m) {
solver.add(id[i][j], id[i + 1][j + 1], K);
} else {
solver.add(id[i][j], T, K);
}
}
}
printf("%lld\n", s - solver.solve());
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest 225beginner atcoder contest 225 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310