【CodeVS 1922】骑士共存问题 / 题解

【CodeVS 1922】骑士共存问题 / 题解

洛谷原题

CodeVS 原题

题目描述

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

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

输入格式

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

输出格式

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

思路

看图。
选了黄色的相应的红色块就不能选。
在这样的点对之间连边得到二分图。
最多能放置的骑士就是这张二分图的最小顶点覆盖。
网络流跑一遍即可(实际上匈牙利也是可以的,最小顶点覆盖等于二分图的最大匹配,证明)。

代码

#include 
#define inf 1e9
#define maxn 400000
#define id(i,j) ((i-1)*n+j)
using namespace std;
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-'0';ch=getchar();}
    return x*f;
}
struct Edge{
    int to,next,val;
    Edge(int a=0,int b=0,int c=0){
        to=a,next=b,val=c;
    }
}l[maxn];
int head[maxn],s,t,n,m,cnt=1,deep[maxn];
int cur[maxn],maxflow,ava[202][202];
int dx[8]={1,1,2,2,-1,-1,-2,-2};
int dy[8]={2,-2,-1,1,-2,2,1,-1}; 
void add(int a,int b,int c){
    l[++cnt]=Edge(b,head[a],c);
    head[a]=cnt;
}
bool bfs(){
    memset(deep,0x7f,sizeof(deep));
    queueq;
    q.push(s);deep[s]=0;
    for (int i=0;i<=n*n+1;i++) cur[i]=head[i];
    while(!q.empty()){
        int hq=q.front();q.pop();
        for (int i=head[hq];i;i=l[i].next){
            int v=l[i].to;
            if (deep[v]>inf&&l[i].val)
                deep[v]=deep[hq]+1,q.push(v);
        }
    }
    return deep[t]n||ny<1||ny>n||ava[nx][ny]) continue;
                    add(id(i,j),id(nx,ny),inf),add(id(nx,ny),id(i,j),0);
                }
            }
            else{
                add(t,id(i,j),0);
                add(id(i,j),t,1);
            }
        }

    }
    dinic();
    cout<
Show Comments