Cogs 746. [网络流24题] 骑士共存(最大独立集)

[网络流24题] 骑士共存

★★☆ 输入文件：knight.in 输出文件：knight.out 简单对比

时间限制：1 s 内存限制：128 MB

骑士共存问题

«问题描述：

在一个n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘

上某些方格设置了障碍，骑士不得进入。

«编程任务：

对于给定的n*n个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑

士，使得它们彼此互不攻击。

«数据输入：

由文件knight.in给出输入数据。第一行有2 个正整数n 和m (1<=n<=200, 0<=m<=n*n)

分别表示棋盘的大小和障碍数。接下来的m 行给出障碍的位置。每行2 个正整数，表示障

碍的方格坐标。

«结果输出:

将计算出的共存骑士数输出到文件knight.out。

输入文件示例输出文件示例

knight.in

3 2

1 1

3 3

knight.out

5

/*

最大独立集问题.

跑二分图匹配.

建图比较鬼畜.

注意边的编号问题.

ans=V-最大匹配数.

dinic即可.

(证明自行百度)

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define MAXN 210

using namespace std;

int dis[MAXN*MAXN+10],n,cut=1,ans,tot,m,max1=1e9,head[MAXN*MAXN+10];

struct data{int v,next,c;}e[MAXN*MAXN*10];

bool b[MAXN][MAXN];

void add(int u,int v,int c)

{

    e[++cut].v=v;

    e[cut].c=c;

    e[cut].next=head[u];

    head[u]=cut;

}

inline int 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-48,ch=getchar();

    return x*f;

}

bool bfs()

{

    memset(dis,-1,sizeof dis);

    queue<int>q;

    q.push(0);

    dis[0]=0;

    while(!q.empty())

    {

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

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]==-1&&e[i].c)

            {

                dis[v]=dis[u]+1;

                q.push(v);

            }

        }

    }

    return dis[n*n+1]!=-1;

}

int dfs(int u,int y)

{

    if(u==n*n+1) return y;

    int rest=0;

    for(int i=head[u];i&&rest<y;i=e[i].next)

    {

        int v=e[i].v;

        if(dis[v]==dis[u]+1&&e[i].c)

        {

            int x=dfs(v,min(e[i].c,y-rest));

            rest+=x;

            e[i].c-=x;

            e[i^1].c+=x;

        }

    }

    if(!rest) dis[u]=-1;

    return rest;

}

void dinic(int s,int t)

{

    while(bfs()) ans+=dfs(s,max1);

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

    return ;

}

void slove()

{

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

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

            if(b[i][j])continue;

            if(i+j&1) add((i-1)*n+j,n*n+1,1),add(n*n+1,(i-1)*n+j,0);

            else add(0,(i-1)*n+j,1),add((i-1)*n+j,0,1);

        }

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

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

      {

        if(i+j&1&&b[i][j]) continue;

        if(i+1<=n&&j+2<=n&&!b[i+1][j+2])

          add((i-1)*n+j,i*n+j+2,1),add(i*n+j+2,(i-1)*n+j,0);

        if(i+2<=n&&j+1<=n&&!b[i+2][j+1])

          add((i-1)*n+j,(i+1)*n+j+1,1),add((i+1)*n+j+1,(i-1)*n+j,0);

        if(i>=2&&j>=3&&!b[i-1][j-2])

          add((i-1)*n+j,(i-2)*n+j-2,1),add((i-2)*n+j-2,(i-1)*n+j,0);

        if(i>=3&&j>=2&&!b[i-2][j-1])

          add((i-1)*n+j,(i-3)*n+j-1,1),add((i-3)*n+j-1,(i-1)*n+j,0);

        if(i>=3&&j+1<=n&&!b[i-2][j+1])

          add((i-1)*n+j,(i-3)*n+j+1,1),add((i-3)*n+j+1,(i-1)*n+j,0);

        if(i>=2&&j+2<=n&&!b[i-1][j+2])

          add((i-1)*n+j,(i-2)*n+j+2,1),add((i-2)*n+j+2,(i-1)*n+j,0);

        if(i+2<=n&&j>=2&&!b[i+2][j-1])

          add((i-1)*n+j,(i+1)*n+j-1,1),add((i+1)*n+j-1,(i-1)*n+j,0);

        if(i+1<=n&&j>=3&&!b[i+1][j-2])

          add((i-1)*n+j,i*n+j-2,1),add(i*n+j-2,(i-1)*n+j,0);

      }

}

int main()

{

    freopen("knight.in","r",stdin);

    freopen("knight.out","w",stdout);

    int x,y;

    n=read(),m=read();

    for(int i=1;i<=m;i++) x=read(),y=read(),b[x][y]=true;

    slove();

    dinic(0,n*n+1);

    return 0;

}

Knight

Cogs 746. [网络流24题] 骑士共存(最大独立集)