loj 6226. 「网络流 24 题」骑士共存问题

1. 题目链接

2. 题目描述##

Problem Description

3. 解题思路##

题目中要求如果一个顶点被选择，那么8个方向上的顶点就不能被选择。显然，这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边，那么本题就是一个求最大独立集的问题，而且是一个求二分图的最大独立集的问题。
为什么是二分图呢？可以从下面两条性质来分析：

对于任意节点$u$，不可能经过奇数步回到节点$u$，实际上，这就是 匈牙利算法 Hungary 的进行二分图的判断的主要思想；
按照题目中那个图，将所有顶点划分成红色、黄色两类节点，可以发现同色的节点之间没有边。

而二分图上有很好的性质，比如：

最大匹配数 = 最小点覆盖；

最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数；

DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。

- DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径，满足 DAG 的所有顶点都被覆盖。
- DAG 对应的二分图这样构造：对于 DAG 中的一个顶点 $p$，二分图中有两个顶点 $p$ 和 $p'$，对应 DAG 中的一条有向边 $p\to q$，二分图中有 $p\to q'$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合，$p'$ 属于 $T$ 集合.

…

求二分图的最大匹配数的方法有匈牙利算法（复杂度$\mathcal O(VE)$）和网络流（代表算法就是Dinic/Hopcroft-carp 算法，复杂度$\mathcal O(\sqrt{V}E)$）。

4. 参考代码##

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 205;
const int MX = MAXN * MAXN; // 点数
const int MS = MX * 8 * 2;  // 边数
template<class T> struct Max_Flow {
    int n;
    int Q[MX], sign;
    int head[MX], level[MX], cur[MX], pre[MX];
    int nxt[MS], pnt[MS], E;
    T cap[MS];
    void Init(int n) {
        E = 0, this->n = n + 1;
        fill(head, head + this->n, -1);
    }
    void Add(int from, int to, T c, T rw = 0) {
        pnt[E] = to, cap[E] = c;
        nxt[E] = head[from], head[from] = E++;
        pnt[E] = from, cap[E] = rw;
        nxt[E] = head[to], head[to] = E++;
    }
    bool BFS(int s, int t) {
        sign = t;
        fill(level, level + n, -1);
        int *front = Q, *tail = Q;
        *tail++ = t;
        level[t] = 0;
        while (front < tail && level[s] == -1) {
            int u = *front++;
            for (int e = head[u]; e != -1; e = nxt[e]) {
                if (cap[e ^ 1] > 0 && level[pnt[e]] < 0) {
                    level[pnt[e]] = level[u] + 1;
                    *tail++ = pnt[e];
                }
            }
        }
        return level[s] != -1;
    }
    void Push(int t, T &flow) {
        T mi = inf;
        for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {
            mi = min(mi, cap[p]);
        }
        for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {
            cap[p] -= mi;
            cap[p ^ 1] += mi;
            if (!cap[p]) sign = pnt[p ^ 1];
        }
        flow += mi;
    }
    void DFS(int u, int t, T &flow) {
        if (u == t) {
            Push(t, flow);
            return;
        }
        for (int &e = cur[u]; e != -1; e = nxt[e]) {
            if (cap[e] > 0 && level[u] - 1 == level[pnt[e]]) {
                pre[pnt[e]] = e;
                DFS(pnt[e], t, flow);
                if (level[sign] > level[u]) return;
            }
        }
        sign = t;
    }
    T Dinic(int s, int t) {
        pre[s] = -1;
        T flow = 0;
        while (BFS(s, t)) {
            copy(head, head + n, cur);
            DFS(s, t, flow);
        }
        return flow;
    }
};
Max_Flow<int> mflow;

const int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int n, m, src, dst;
vector<bool> flag, used;

void dfs(int x, int y, bool f) {
    int u = (x - 1) * n + y;
    used[u] = true;
    if(!f) mflow.Add(src, u, 1);
    else mflow.Add(u, dst, 1);
    for(int d = 0; d < 8; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 1 || ny < 1 || nx > n || ny > n) continue;
        int v = (nx - 1) * n + ny;
        if(flag[v]) continue;
        if(!f) mflow.Add(u, v, 1);
        if(used[v]) continue;
        dfs(nx, ny, f ^ 1);
    }
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input.txt", "r", stdin);
#endif
    while(~scanf("%d %d", &n, &m)) {
        flag = vector<bool>(n * n + 1, false);
        for(int i = 1; i <= m; ++i) {
            int x, y; scanf("%d %d", &x, &y);
            flag[(x - 1) * n + y] = true;
        }
        src = 0, dst = n * n + 1;
        mflow.Init(n * n + 2);
        used = vector<bool>(n * n + 1, false);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                int u = (i - 1) * n + j;
                if(flag[u] || used[u]) continue;
                dfs(i, j, 0);
            }
        }
        int num = 0;
        for(int i = 1; i <= n * n; ++i) num += !flag[i];
        int mf = mflow.Dinic(src, dst);
        cout << num - mf << endl;
    }
    return 0;
}