洛谷原题
CodeVS 原题
题目描述
在一个 $n*n$ 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入。
对于给定的 $n*n$ 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。
输入格式
第一行有 2 个正整数n 和 m (1<=n<=100)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。
输出格式
将计算出的共存骑士数输出。
思路
看图。
选了黄色的相应的红色块就不能选。
在这样的点对之间连边得到二分图。
最多能放置的骑士就是这张二分图的最小顶点覆盖。
网络流跑一遍即可（实际上匈牙利也是可以的，最小顶点覆盖等于二分图的最大匹配，证明）。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <bits/stdc++.h> #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)); queue<int>q; 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]<inf; } int dfs(int u,int limt){ if (!limt||u==t) return limt; int flow=0,f; for (int i=cur[u];i;i=l[i].next){ int v=l[i].to;cur[u]=i; if (deep[v]==deep[u]+1&&(f=dfs(v,min(limt,l[i].val)))){ limt-=f; flow+=f; l[i].val-=f; l[i^1].val+=f; if (!limt) break; } } return flow; } void dinic(){ while (bfs()) maxflow+=dfs(s,inf); } int main(){ ios::sync_with_stdio(false); n=read(),m=read();t=n*n+1; for (int i=1;i<=m;i++) ava[read()][read()]=1; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ if (ava[i][j]) continue; if ((i+j)&1){ add(s,id(i,j),1); add(id(i,j),s,0); for (int dir=0;dir<8;dir++){ int nx=i+dx[dir],ny=j+dy[dir]; if (nx<1||nx>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<<n*n-m-maxflow; } |