题解 P4474 【王者之剑】

Ireliaღ

2019-07-19 09:41:52

Solution

教练留的网络流作业,我看见$Saber$就冲进来了,能看到这么一道题月厨深感欣慰。 然后看题。诶?跟方格取数一样的,写一发`ISAP`就切了。 ## 建图 - 设$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$ 然后跑最大流,用数字总和减去它即可。 ## 代码 指针版`ISAP`,有当前弧优化 ```cpp // 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) { head[u] = new Edge(v, w, head[u]); head[v] = new Edge(u, 0, head[v]); head[u]->ops = head[v]; head[v]->ops = head[u]; } 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; } } cur[u] = head[u]; gap[dep[u]]--; if (gap[dep[u]] == 0) dep[s] = n * m + 3; dep[u]++; gap[dep[u]]++; return used; } void Work() { memcpy(cur, head, sizeof(head)); 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) { AddEdge(0, ID(i, j), num[i][j]); 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; } ``` ~~如果做过方格取数的话,直接拷贝进来就A了,注意下数组大小~~