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

洛谷原题

CodeVS 原题

题目描述

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

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

输入格式

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

输出格式

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

思路

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

代码

#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]; head[maxn],s,t,n,m,cnt="1,deep[maxn];" cur[maxn],maxflow,ava[202][202]; dx[8]="{1,1,2,2,-1,-1,-2,-2};" 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){" 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<