题解 P3355 【骑士共存问题】

Ireliaღ

2019-04-10 17:36:14

Solution

**最大流=最小割** ISAP+当前弧优化巨快 ### 解题思路 不难看出,马能攻击到的点和它本身所在的点黑白颜色不同,所以我们考虑建立二分图进行匹配 ### 建图 * 设$0$为原点,$n ^ 2 + 1$为汇点,把格子上的每一个点映射到$[1, n ^ 2]$ * 对于$\forall i \in black$,如果**$i$点没有障碍**,从$0$向$i$建立容量为$1$的边 * 对于$\forall j \in white$,如果**$j$点没有障碍**,从$j$向$n ^ 2 + 1$建立容量为$1$的边 * 对于$\forall i \in black$,从$i$向能攻击到的八个白点建立容量为$\infty$的边 然后跑最大流,用总格数-障碍数-最大流即可 ### 代码 看有人发匈牙利和dinic的题解,说奇数建图和偶数建图有一种过不了,但是用ISAP两种都能过。 ```cpp // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int MAXN = 205; const int INF = 0x3f3f3f3f; const int DIRX[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; const int DIRY[8] = {-1, -2, -2, -1, 1, 2, 2, 1}; int n, m; bool trap[MAXN][MAXN]; int ID(int x, int y) { return (x - 1) * n + y; } 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]; 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], 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) { used += mi; e->val -= mi; e->ops->val += mi; } if (used == flow) return used; } } gap[dep[u]]--; cur[u] = head[u]; if (gap[dep[u]] == 0) dep[s] = n * n + 3; dep[u]++; gap[dep[u]]++; return used; } void Work() { memcpy(cur, head, sizeof(head)); res = 0; Bfs(); while (dep[s] <= n * n + 2) Dfs(s, INF); } int main() { ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; s = 0; t = n * n + 1; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; trap[x][y] = true; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if ((i + j) % 2 == 0) { if (!trap[i][j]) AddEdge(0, ID(i, j), 1); for (int k = 0; k < 8; k++) { int x = i + DIRX[k], y = j + DIRY[k]; if (x < 1 || x > n || y < 1 || y > n) continue; AddEdge(ID(i, j), ID(x, y), INF); } } else { if (!trap[i][j]) AddEdge(ID(i, j), n * n + 1, 1); } } } Work(); cout << n * n - m - res << endl; return 0; } ```