网络流24题之二十四 骑士共存问题

坑填完了，可喜可贺

地址：luogu3355

题目描述

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

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

输入输出格式

输入格式：

第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。

输出格式：

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

输入输出样例

3 2
1 1
3 3

5

模型

二分图最大独立集，转化为二分图最大匹配，从而用最大流解决。

实现

首先把棋盘黑白染色，使相邻格子颜色不同。

把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。

建立附加源S汇T，从S向X集合中每个顶点连接一条容量为1的有向边，从Y集合中每个顶点向T连接一条容量为1的有向边。

从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。

求出网络最大流，要求的结果就是可用格子的数量减去最大流量。

分析

用网络流的方法解决棋盘上的问题，一般都要对棋盘黑白染色，使之成为一个二分图。放尽可能多的不能互相攻击的骑士，就是一个二分图最大独立集问题。有关二分图最大独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。

该题规模比较大，需要用效率较高的网络最大流算法解决。（使用Dinic+当前弧优化）

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 210*210
#define N 210
#define INF 0x3f3f3f3f
#define min(x,y) ((x<y)?(x):(y))
//#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
using namespace std;
//char BB[1 << 15], *S = BB, *T = BB;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int from,to,next,flow;
}e[M*10];
int tot=-1,st[M*10],dis[M],cur[M*10];
int n,m,x,y,z;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z)
{add(x,y,z),add(y,x,0);}
int bfs(int s,int t)
{
    for(int i=0;i<=n*n+1;i++)
        cur[i]=st[i];
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=cur[x];~i;i=e[i].next)
    {
        cur[x]=i;
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            return ans;
        }
    }

    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
//首先把棋盘黑白染色，使相邻格子颜色不同。
//把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。建立附加源S汇T，
//从S向X集合中每个顶点连接一条容量为1的有向边，从Y集合中每个顶点向T连接一条容量为1的有向边。
//从每个可用的黑色格子向骑士一步能攻击到的可用的白色格子连接一条容量为无穷大的有向边。
//求出网络最大流，要求的结果就是可用格子的数量减去最大流量。
int map[N][N];
main()
{
    int wait,sum=0;
    int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};
    n=read(),m=read();
    int S=0,T=n*n+1;
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    for (int i=1;i<=m;i++)
        x=read(),y=read(),map[x][y]=-1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (!map[i][j])
            {
                map[i][j]=++sum;
                if ((i+j)%2==0)
                    add_edge(S,sum,1);
                else
                    add_edge(sum,T,1);
            }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (map[i][j]!=-1 && (i+j)%2==0)
                for (int k=0;k<8;k++)
                    if (i+dx[k]>=1 && i+dx[k]<=n && j+dy[k]>=1 && j+dy[k]<=n && map[i+dx[k]][j+dy[k]]!=-1)
                        add_edge(map[i][j],map[i+dx[k]][j+dy[k]],INF);
    printf("%d\n",n*n-m-Dinic(S,T));
}