洛谷P2774|洛谷P2774 方格取数问题
洛谷P2774方格取数问题 【洛谷P2774|洛谷P2774 方格取数问题】题目链接
将题目反着考虑，假设现在所有数都取，需要删掉一部分数，使得剩下的数没有公共边且删掉的数之和最小。
容易发现，两个位置有公共边当且仅当他们横纵坐标的和的奇偶性不同。建立一个二分图，左边为坐标和为奇数的点，右边为坐标和为偶数的点，将左右两边存在公共边的点连起来。s向左边的每个点建边，权值为点的权值，右边每个点向t建边，权值也为点的权值。求删掉和最少的数使得剩下的数没有公共边就是求上面所建的图的最小割。
#include using namespace std;
const int maxn = 1e4;
const int maxm = 1e6;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Dinic {
struct Edge {
int next, to;
ll f;
} e[maxm];
int head[maxn];
ll dep[maxn], tol;
ll ans;
int cur[maxn];
int src, sink, n;
void add(int u, int v, int f) {
tol++;
e[tol].to = v;
e[tol].next = head[u];
e[tol].f = f;
head[u] = tol;
tol++;
e[tol].to = u;
e[tol].next = head[v];
e[tol].f = 0;
head[v] = tol;
}bool bfs() {
queue q;
for (int i = 0;
i <= n;
++i) dep[i] = -1;
q.push(src);
dep[src] = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
for (int i = head[now];
i;
i = e[i].next) {
if (dep[e[i].to] == -1 && e[i].f) {
dep[e[i].to] = dep[now] + 1;
if (e[i].to == sink)
return true;
q.push(e[i].to);
}
}
}
return false;
}ll dfs(int x, ll maxx) {
if (x == sink)
return maxx;
for (int &i = cur[x];
i;
i = e[i].next) {//当前弧优化
if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) {
ll flow = dfs(e[i].to, min(maxx, e[i].f));
//多路增广
if (flow) {
e[i].f -= flow;
e[i ^ 1].f += flow;
return flow;
}
}
}
return 0;
}ll dinic(int s, int t) {
ans = 0;
this->src = https://www.it610.com/article/s;
this->sink = t;
while (bfs()) {
for (int i = 0;
i <= n;
++i)
cur[i] = head[i];
while (ll d = dfs(src, inf))
ans += d;
}
return ans;
}void init(int n) {
this->n = n;
for (int i = 0;
i <= n;
++i)head[i] = 0;
tol = 1;
}
} G;
int n, m;
int getpos(int i, int j) {
return (i - 1) * m + j;
}int main() {
cin >> n >> m;
int val;
int sum = 0, ans;
int s = 0, t = n * m + 1;
G.init(t);
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= m;
j++) {
cin >> val;
sum += val;
if ((i + j) % 2) {
G.add(s, getpos(i, j), val);
if (i - 1 >= 1)
G.add(getpos(i, j), getpos(i - 1, j), inf);
if (j - 1 >= 1)
G.add(getpos(i, j), getpos(i, j - 1), inf);
if (i + 1 <= n)
G.add(getpos(i, j), getpos(i + 1, j), inf);
if (j + 1 <= m)
G.add(getpos(i, j), getpos(i, j + 1), inf);
} else {
G.add(getpos(i, j), t, val);
}
}
}
ans = G.dinic(s, t);
cout << sum - ans << endl;
return 0;
} 推荐阅读
- 【读书清单|【读书清单 05】《聪明人用方格笔记本》2
- 洛谷 P5056 【模板】插头dp
- 聪明人用方格笔记本
- C++|【暖*墟】 #洛谷省选网课# 8.1数论进阶
- 洛谷|洛谷 P1481 魔族密码
- SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)
- KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）
- JSOI2018冬令营游记&总结（迁移自洛谷博客）
- 洛谷P5471 NOI2019弹跳
- 豆包今日践行~20171031