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

题目描述

在一个 n×n\text{n} \times \text{n}n×n 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。

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

对于给定的 n×n\text{n} \times \text{n}n×n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。

输入格式

第一行有两个正整数 n\text{n}n 和 m\text{m}m (1≤n≤200,0≤m≤n2−1)( 1 \leq n \leq 200, 0 \leq m \leq n^2 - 1 )(1≤n≤200,0≤m≤n2−1) 分别表示棋盘的大小和障碍数。

输出格式

输出计算出的共存骑士数。

样例

样例输入

样例输出

数据范围与提示

1≤n≤2001\leq n\leq 2001≤n≤200

0≤m≤n2−10 \leq m \leq n^2-10≤m≤n2−1

/*

    加了当前弧优化和读入优化，快了不少

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 40010

#define INF 1000000000

int n,m,head[maxn],dis[maxn],num=,S,T,cur[maxn];

bool vis[maxn],mark[maxn];

struct node{int to,pre,v;}e[maxn*];

using namespace std;

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

void Insert(int from,int to,int v){

    e[++num].to=to;e[num].v=v;e[num].pre=head[from];head[from]=num;

    e[++num].to=from;e[num].v=;e[num].pre=head[to];head[to]=num;

}

bool bfs(){

    for(int i=S;i<=T;i++)dis[i]=-,cur[i]=head[i];

    queue<int>q;

    q.push(S);dis[S]=;

    while(!q.empty()){

        int now=q.front();q.pop();

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(e[i].v>&&dis[to]==-){

                dis[to]=dis[now]+;

                if(to==T)return ;

                q.push(to);

            }

        }

    }

    return dis[T]!=-;

}

int dinic(int x,int flow){

    if(x==T||flow==){return flow;}

    int rest=flow;

    for(int &i=cur[x];i;i=e[i].pre){

        int to=e[i].to;

        if(dis[to]==dis[x]+&&e[i].v>){

            int delta=dinic(to,min(rest,e[i].v));

            e[i].v-=delta;

            e[i^].v+=delta;

            rest-=delta;

        }

    }

    return flow-=rest;

}

bool check(int x,int y){

    if(x<=n&&x>=&&y<=n&&y>=&&!mark[count(x,y)])return ;

    return ;

}

int qread(){

    int i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i*j;

}

int main(){

    n=qread();m=qread();

    S=,T=n*n+;

    int x,y;

    for(int i=;i<=m;i++){

        x=qread();y=qread();

        mark[count(x,y)]=;

    }

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            if(mark[count(i,j)])continue;

            if((i+j)&){

                Insert(S,count(i,j),);

                if(check(i-,j-))Insert(count(i,j),count(i-,j-),);

                if(check(i-,j+))Insert(count(i,j),count(i-,j+),);

                if(check(i+,j-))Insert(count(i,j),count(i+,j-),);

                if(check(i+,j+))Insert(count(i,j),count(i+,j+),);

                if(check(i-,j-))Insert(count(i,j),count(i-,j-),);

                if(check(i-,j+))Insert(count(i,j),count(i-,j+),);

                if(check(i+,j-))Insert(count(i,j),count(i+,j-),);

                if(check(i+,j+))Insert(count(i,j),count(i+,j+),);

            }

            else Insert(count(i,j),T,);

        }

    }

    int ans=;

    while(bfs())ans+=dinic(S,INF);

    printf("%d",n*n-ans-m);

}

秒客网