Irelia

题解 P4474 【王者之剑】

posted on 2019-07-19 09:41:52 | under 题解 |

建图

• 设 $0$ 为原点， $n \times m + 1$ 为汇点，把棋盘里的点全部映射到 $[1, n \times m]$ 的节点
• 对于 $\forall i \in black$ ，从 $0$ 向 $i$ 建边，容量为该点数字
• 对于 $\forall j \in white$ ，从 $j$ 向 $n \times m + 1$ 建边，容量为该点数字
• 对于 $\forall i \in black$ ，从 $i$ 向上下左右的白点建边，容量为 $\infty$

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int m, n;

struct Edge{
int to, val;
Edge *next, *ops;
Edge(int to, int val, Edge *next): to(to), val(val), next(next){}
};

Edge *head[MAXN * MAXN], *cur[MAXN * MAXN];

int ID(int x, int y) {
return (x - 1) * n + y;
}

void AddEdge(int u, int v, int w) {
}

int dep[MAXN * MAXN], gap[MAXN * MAXN];
int s, t, res;

void Bfs() {
memset(dep, -1, sizeof(dep));
memset(gap, 0, sizeof(gap));
dep[t] = 0; gap[0]++;
queue<int> q; q.push(t);
while (!q.empty()) {
int u = q.front(); q.pop();
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (dep[v] != -1) continue;
q.push(v);
dep[v] = dep[u] + 1;
gap[dep[v]]++;
}
}
}

int Dfs(int u, int flow) {
if (u == t) {
res += flow;
return flow;
}
int used = 0;
for (Edge *&e = cur[u]; e; e = e->next) {
int v = e->to;
if (e->val && dep[v] == dep[u] - 1) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
used += mi;
}
if (used == flow) return used;
}
}
gap[dep[u]]--;
if (gap[dep[u]] == 0) dep[s] = n * m + 3;
dep[u]++;
gap[dep[u]]++;
return used;
}

void Work() {
res = 0;
Bfs();
while (dep[s] <= n * m + 2) Dfs(s, INF);
}

int num[MAXN][MAXN];

int main() {
ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> m >> n;
s = 0; t = n * m + 1;
int sum = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> num[i][j], sum += num[i][j];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if ((i + j) % 2 == 1) {
if (i > 1) AddEdge(ID(i, j), ID(i - 1, j), INF);
if (i < m) AddEdge(ID(i, j), ID(i + 1, j), INF);
if (j > 1) AddEdge(ID(i, j), ID(i, j - 1), INF);
if (j < n) AddEdge(ID(i, j), ID(i, j + 1), INF);
} else {
AddEdge(ID(i, j), n * m + 1, num[i][j]);
}
}
}
Work();
cout << sum - res << endl;
return 0;
}