题解 | 算法竞赛进阶指南 骑士放置

思路

很明显,一对相斥的位置,横纵坐标之和的奇偶性肯定不同.所以可以构成一个二分图.
源点向所有横纵坐标之和为奇数的点连边,为偶数的向汇点连边,边权都为1.
一对相斥的点之间连边,跑一遍最小割即可.
或者如果你懒得写网络流,你可以套用最大独立点集的模型,跑匈牙利即可.虽然效率比网络流低得多.

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 60555
#define MAXM 520555

int N, M, TT;
int hd[MAXN], val[MAXM], nxt[MAXM], to[MAXM], tot(1);
int cur[MAXN];
int S, T, x, y;
bool mp[205][205];

void Add( int x, int y, int z ){
    nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; val[tot] = z;
    nxt[++tot] = hd[y]; hd[y] = tot; to[tot] = x; val[tot] = 0;
}

int d[MAXN]; queue<int> Q;

bool BFS(){
    while( !Q.empty() ) Q.pop();
    memset( d, 0, sizeof d ); d[S] = 1; Q.push(S);
    while( !Q.empty() ){
        int t(Q.front()); Q.pop();
        for ( int i = hd[t]; i; i = nxt[i] ){
            if ( val[i] && !d[to[i]] ){
                d[to[i]] = d[t] + 1; Q.push(to[i]);
                if ( to[i] == T ) return 1;
            }
        }
    }
    return 0;
}

int DFS( int x, int fl ){
    if ( x == T ) return fl;
    int res(fl), k;
    for ( int &i = cur[x]; i && res; i = nxt[i] ){
        if ( val[i] && d[to[i]] == d[x] + 1 ){
            k = DFS( to[i], min( res, val[i] ) );
            if ( !k ) d[to[i]] = 0;
            res -= k; val[i] -= k; val[i ^ 1] += k;
        }
    }
    return fl - res;
}

int GetID( int x, int y ){ return ( x - 1 ) * M + y; }
int dir[][2] = { 1, 2, 2, 1, -1, -2, -2, -1, -1, 2, 2, -1, 1, -2, -2, 1 };

int main(){
    scanf( "%d%d%d", &N, &M, &TT );
    for ( int i = 1; i <= TT; ++i ) scanf( "%d%d", &x, &y ), mp[x][y] = 1;
    S = 0; T = N * M + 1;
    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= M; ++j ){
            if ( mp[i][j] ) continue;

            if ( ( i ^ j ) & 1 ) Add( S, GetID( i, j ), 1 );
            else{
                Add( GetID( i, j ), T, 1 );
                for ( int k = 0; k < 8; ++k ){
                    int tx(i + dir[k][0]), ty(j + dir[k][1]);
                    if ( tx > 0 && ty > 0 && tx <= N && ty <= M && !mp[tx][ty] ) Add( GetID( tx, ty ), GetID( i, j ), INT_MAX );
                }
            }
        }
    int ans( N * M - TT ), k;
    while( BFS() ){
        memcpy( cur, hd, sizeof hd );
        while( ( k = DFS( S, INT_MAX ) ) ) ans -= k;
    }
    printf( "%d\n", ans );
    return 0;
}