【二分图最大独立集/最小割】P3355 骑士共存问题

P3355 骑士共存问题

思路

为方便表述，定义奇数点为横纵坐标之和为奇数的点，偶数点为横纵坐标之和为偶数的点。

观察可以发现，骑士可以：只放在奇数点上，或只放在偶数点上。当一个骑士放在奇数点上时，不影响任何奇数点，而影响一部分偶数点；若这些偶数点被放置了骑士，该奇数点也在攻击范围内。

从中可以抽象出二分图模型：让奇数点为左部点，偶数点为右部点，能互相攻击到的奇数点与偶数点之间连一条单向边。则问题转化为求满足内部任意两顶点互不相邻的顶点数最多的顶点集合，即二分图最大独立集。

又二分图最大独立集=顶点总数-最大匹配数，最大匹配可以用KM跑，也可以用Dinic求最大流。这里选择用后者，故所有的奇数点（左部点）(L_i)与源点(S)有一条有向边(S→L_i)；所有的偶数点（右部点）(R_i)与汇点(T)有一条有向边(R_i→T)，能相互攻击到的奇数点(L_{ai})和偶数点(R_{ai})之间连一条有向边(L_{ai}→R_{ai})，建图完成。

代码

void addn(int u, int v, LL w) {
    //网络流建图
    e[++cnt_e].next = head[u]; e[cnt_e].from = u; e[cnt_e].to = v; e[cnt_e].w = w; head[u] = cnt_e;
    e[++cnt_e].next = head[v]; e[cnt_e].from = v; e[cnt_e].to = u; e[cnt_e].w = 0; head[v] = cnt_e;
}

int dirx[] = { 1,1,-1,-1,2,2,-2,-2 };
int diry[] = { -2,2,-2,2,1,-1,1,-1 };

void bfs() {
    mem(depth, -1);
    mem(gap, 0);
    depth[t] = 0;
    gap[0] = 1;
    cur[t] = head[t];
    queue<int> q;
    q.push(t);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (depth[v] != -1) continue;
            q.push(v);
            depth[v] = depth[u] + 1;
            gap[depth[v]]++;
        }
    }
    return;
}

LL dfs(int now, LL minflow,int n) {
    if (now == t) {
        Maxflow += minflow;
        return minflow;
    }
    LL nowflow = 0;
    for (int i = cur[now]; i; i = e[i].next) {
        cur[now] = i;
        int v = e[i].to;
        if (e[i].w && depth[v] + 1 == depth[now]) {
            LL k = dfs(v, min(e[i].w, minflow - nowflow), n);
            if (k) {
                e[i].w -= k;
                e[i ^ 1].w += k;
                nowflow += k;
            }
            if (minflow == nowflow) return nowflow;
        }
    }
    gap[depth[now]]--;
    if (!gap[depth[now]]) depth[s] = n + 1;
    depth[now]++;
    gap[depth[now]]++;
    return nowflow;
}

LL ISAP(int n) {
    Maxflow = 0;
    bfs();
    while (depth[s] < n) {
        memcpy(cur, head, sizeof(head));
        dfs(s, INF, n);
    }
    return Maxflow;
}

bool ok(int x, int y) {
    if (x<1 || x>n) return false;
    if (y<1 || y>n) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    n = read(); m = read();
    s = n * n + 1; t = n * n + 2;
    //啊这……好像会和格子的点重复……
    cnt_e = 1;
    f(i, 1, m) {
        int x, y; x = read(); y = read();
        ban[(x - 1) * n + y] = 1;
    }
    //黄格子连源点，红格子连汇点
    //也就是将棋盘（除了有障碍的）放满骑士
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int pos = (i - 1) * n + j;
            if (!ban[pos]) {
                if ((i + j) & 1) addn(pos, t, 1);
                //pos%2不一定红黄相间！！(i+j)%2才能保证！！
                else{
                    addn(s, pos, 1);
                    //因为骑士全放红/黄格子肯定没问题（攻击区域都是异色格子）
                    //所以这里选择黄格子全部放满，对于每个黄格子，向它的可攻击格子连边。
                    int x, y;
                    for (int k = 0; k < 8; k++) {
                        x = i + dirx[k]; y = j + diry[k];
                        if (ok(x, y)) addn(pos, (x - 1) * n + y, INF);
                        //if (ok(x, y)) addn((x - 1) * n + y, pos, INF);
                    }
                }
            }
        }
    }
    int mincost = ISAP(n * n + 2);
    cout << n * n - m - mincost;
    return 0;
}