「Luogu P4304」「TJOI2013」攻击装置

Description

给定一个大小为 $n \times n$ 的 $01$ 矩阵，其中你可以在 $0$ 的位置放置攻击装置。每一个攻击装置 $(x,y)$ 都可以按照“日”字攻击其周围的 $8$ 个位置。求在装置互不攻击的情况下，最多可以放置多少个装置。

$(1 \leq n \leq 200)$

Source

[Luogu]P4304

Solution

与 网络流 24 题 中的 骑士共存问题 几乎一样。

我们可以先将棋盘染色，得到

对于格子 $(x,y)$，若 $x + y$ 是奇数，则该格子为白色，否则为黑色。

很容易发现，放在白（黑）色格子上的攻击装置只能攻击到黑（白）色格子。

那么显然这是一个二分图。

我们把白色格子和黑色格子分成两部分。

如果某个白色格子可以攻击到某个黑色格子，则在它们之间连一条边。

一条边所连接的两个格子只能取其中一个（否则会互相攻击），所以问题变为求这个二分图的 最大独立集 。

最大独立集 = 总点数 - 最小点覆盖 = 总点数 - 最大匹配数

至于不能放攻击装置的格子，我们不把它当做二分图中的点即可，最后答案要减去这些点。

所以用 $\rm dinic$ 跑一遍最小割（最大流）就能够得到答案了。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

inline void readDigit(bool &x) {
    x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar());
    x = c ^ 48;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXP = 200, MAXN = 5e4, MAXM = 1e6, INF = 0x3f3f3f3f;
const int dx[8] = { 1, 2, -1, -2, -1, 2, 1, -2 };
const int dy[8] = { 2, 1, -2, -1, 2, -1, -2, 1 };
int n, tot = 1, sum, id[MAXP + 5][MAXP + 5], head[MAXN + 5];
int cur[MAXN + 5], depth[MAXN + 5];
bool f[MAXP + 5][MAXP + 5];
struct Edge {
    int next, to, dis;
} e[MAXM + 5];

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge) { head[u], v, w };
    head[u] = tot;
}

inline void build(int x, int y) {
    for (int i = 0; i < 8; ++i) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || ty < 1 || tx > n || ty > n || f[tx][ty]) continue;
        addEdge(id[x][y], id[tx][ty], INF), addEdge(id[tx][ty], id[x][y], 0);
        //如果 (x,y) 能攻击到点 (tx,ty)，则在它们之间连一条边 
    }
}

inline bool bfs(int s, int t) {//找增广路 
    for (int i = 0; i <= t; ++i) cur[i] = head[i];
    memset(depth, 0, sizeof (depth));
    queue<int> q;
    depth[s] = 1;
    q.push(s);
    for (; !q.empty(); ) {
        int u = q.front();
        q.pop();
        for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
            if (depth[v] || !w) continue;
            depth[v] = depth[u] + 1;
            if (v == t) return 1;
            q.push(v);
        }
    }
    return 0;
}

int dinic(int u, int t, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int v, w, i = cur[u]; v = e[i].to, w = e[i].dis, i && rest; i = e[i].next) {
        cur[u] = i;//当前弧优化 
        if (depth[v] != depth[u] + 1 || !w) continue;
        int k = dinic(v, t, min(rest, w));
        if (!k) depth[v] = 0;
        else {
            e[i].dis -= k;
            e[i ^ 1].dis += k;
            rest -= k;
        }
    }
    return flow - rest;
}

inline int minCut(int s, int t) {//求最小割 
    int res = 0;
    for (; bfs(s, t); ) res += dinic(s, t, INF);
    return res;
}

int main() {
    read(n);
    int s = 0, t = n * n + 1;//超级源点 s 与 超级汇点 t 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            readDigit(f[i][j]);
            sum += f[i][j];//不能放攻击装置的点的数量 
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            id[i][j] = (i - 1) * n + j;//点的编号
            if (f[i][j]) continue;
            if ((i + j) & 1)//源点向白色格子连一条流量为 1 的边 
                addEdge(s, id[i][j], 1), addEdge(id[i][j], s, 0);
            else //黑色格子向汇点连一条流量为 1 的边 
                addEdge(id[i][j], t, 1), addEdge(t, id[i][j], 0);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if ((i + j) & 1) build(i, j);//白色格子与黑色格子连边 
    write(n * n - sum - minCut(s, t));//最大独立集 
    putchar('\n');
    return 0;
}