P3355 骑士共存问题

骑士攻击图天然二分，但不能把障碍当成顶点

问题

P3355 骑士共存问题
在有障碍的 $n\times n$ 棋盘上放尽量多的骑士，任意两匹骑士不能互相攻击。骑士可走 $(\pm1,\pm2)$ 或 $(\pm2,\pm1)$。

数据规模：$1\le n\le200$，$0\le m<n^2$，其中 $m$ 为障碍数。

借用上一题 P2774 方格取数问题 的独立集概念，这题也可以转化为类似的模型。

把每个可以放置骑士的格子看成一个顶点，如果两个格子上的骑士能够互相攻击，就在它们之间连接一条冲突边。

要求放尽量多的骑士，并保证任意冲突边的两个端点不能同时被选择，因此题目就是冲突图上的最大独立集。

而骑士每次移动，一个坐标变化 $1$，另一个坐标变化 $2$，所以 $x+y$ 的奇偶性一定发生改变。因此每一条骑士攻击边都只连接奇格与偶格。按照 $x+y$ 奇偶性染色以后，攻击图天然是一张二分图。

和前面那题一样的是，独立集 的补集就是 点覆盖，所以：最大独立集大小 = 总点数 - 最小点覆盖。

由于本题没有点权，对于无权二分图来说，根据 König 定理：最小点覆盖大小 = 最大匹配大小。

所以设所有可用格数量为 $|V|$，二分图最大匹配大小为 $M$，答案就是：$|V|-M$。

这里既可以直接写匈牙利算法，也可以按照 P2756 飞行员配对方案问题 的单位容量流网络求最大匹配。

与 P2774 不同，本题中间攻击边只承担匹配关系，因此容量直接设为 $1$ 即可，不需要使用表示强制覆盖约束的 inf。

▶

P3355 建图

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

bool a[205][205];
int n, m;

int encode( int x, int y ) {
    return ( x - 1 ) * n + y;
}

int dx[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dy[] = { -1, 1, -2, 2, -2, 2, -1, 1 };

void solve( ) {
    n = read( ), m = read( );
    
    int S = 0, T = n * n + 1;
    init( T );

    for( int i = 1; i <= m; ++ i ) {
        int x = read( ), y = read( );
        a[x][y] = true;
    }
    
    int cnt = 0;
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            if( a[i][j] ) continue;
            cnt ++;
            int id = encode( i, j );
            if( ( i + j ) & 1 ) add_edge( S, id, 1 );
            else add_edge( id, T, 1 );
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            if( ( ( i + j ) & 1 ) == 0 ) continue;
            if( a[i][j] ) continue;
            int id = encode( i, j );
            for( int dir = 0; dir < 8; ++ dir ) {
                int nx = i + dx[dir], ny = j + dy[dir];
                if( nx < 1 || nx > n || ny < 1 || ny > n ) continue;
                if( a[nx][ny] ) continue;
                int nid = encode( nx, ny );
                add_edge( id, nid, 1 );
            }
        }
    }

    ll match = Dinic( S, T, T );
    cout << cnt - match << '\n';
}