loj6226「网络流 24 题」骑士共存问题

loj6226「网络流 24 题」骑士共存问题

(​​ 题目描述

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

233

对于给定的 n×n\text{n} \times \text{n}n×n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。 输入格式

第一行有两个正整数 n\text{n}n 和 m\text{m}m (1≤n≤200,0≤m≤n2−1)( 1 \leq n \leq 200, 0 \leq m \leq n^2 - 1 )(1≤n≤200,0≤m≤n​2​​−1) 分别表示棋盘的大小和障碍数。 输出格式

输出计算出的共存骑士数。 样例 样例输入

3 2 1 1 3 3

样例输出

5

数据范围与提示

1≤n≤2001\leq n\leq 2001≤n≤200

0≤m≤n2−10 \leq m \leq n^2-10≤m≤n2−1

想到棋盘其实就是一个最大点的独立集 首先针对棋盘进行黑白染色 可以证明能攻击的格子是两个互不相交的集合

1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2 1 2 2 1 2 1 2 1 1 2 1 2 1 2 2 1 2 1 2 1

原因我们可以简单证明 设横向绝对值为2纵向绝对值为1 的走法走了 x次 纵向为1 横向为2 的走法走了y次。只有x 与 y 同奇(同偶)才可以使得起点到重点的delta x 与 delta y 同奇(同偶)

关于二分图的最大独立集可以转化为二分图的最大匹配 可以求一下最大割

我首先从源点向所有黑色的点建边 边权为1 然后 再把所有白色的边向汇点建边

然后把这个黑色的点向能够一步范围内攻击到的白点然后权值为1 最后跑一遍最大流即可

二分图的最大独立集

如果一个图是二分图，那么它的最大独立集就是多项式时间可以解决的问题了 |最大独立集| = |V|-|最大匹配数| 证明： 设最大独立集数为U，最大匹配数为M，M覆盖的顶点集合为EM。 为了证明|U|=|V|-|M|，我们分两步证明|U|<=|V|-|M|和|U|>=|V|-|M| 1 先证明 |U|<=|V|-|M| M中的两个端点是连接的，所有M中必有一个点不在|U|集合中，所以|M|<=|V|-|U| 2 再证明|U|>=|V|-|M| 假设(x,y)属于M 首先我们知道一定有|U|>=|V|-|EM|，那么我们将M集合中的一个端点放入U中可以吗？ 假设存在(a,x)，(b,y)，(a,b)不在EM集合中 如果(a,b)连接，则有一个更大的匹配存在，矛盾 如果(a,b)不连接，a->x->y->b有一个新的增广路，因此有一个更大的匹配，矛盾 所以我们可以了解到取M中的一个端点放入U中肯定不会和U中的任何一个点相连，所以|U|>=|V|-|EM|+|M|=|V|-|M| 所以，|U|=|V|-|M|

#include #include#include#include#define inf 0x3f3f3f3f#define N 44000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}struct node{ int y,next,z;}data[N*20];int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1},num=1,h[N],level[N],n,m,id[220][220],tot,T,mp[220][220];inline void insert1(int x,int y,int z){ data[++num].y=y;data[num].next=h[x];data[num].z=z;h[x]=num; data[++num].y=x;data[num].next=h[y];data[num].z=0;h[y]=num;}inline bool bfs(){ queueq;memset(level,0,sizeof(level));level[0]=1;q.push(0); while(!q.empty()){ int x=q.front();q.pop(); for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if(y==T) return 1; } }return 0;}inline int dfs(int x,int s){ if (x==T) return s;int ss=s; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (level[x]+1==level[y]&&z){ int xx=dfs(y,min(s,z));if (!xx) level[y]=0; s-=xx;data[i].z-=xx;data[i^1].z+=xx;if(!s) return ss; } }return ss-s;}int main(){ freopen("3355.in","r",stdin); n=read();m=read();int sum=0; for (int i=1;i<=m;++i){int x=read(),y=read();mp[x][y]=1;} for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) if(!mp[i][j]) id[i][j]=++tot;T=tot+1; for (int i=1;i<=n;++i){ for (int j=1;j<=n;++j){ if (mp[i][j]) continue;sum++; if ((i+j)%2==0) { insert1(0,id[i][j],1); for (int k=0;k<8;++k){ int x1=i+dx[k],y1=j+dy[k];if (x1<1||x1>n||y1<1||y1>n||mp[x1][y1]) continue; if ((x1+y1)%2) insert1(id[i][j],id[x1][y1],1); } }else insert1(id[i][j],T,1); } }int ans=0; while(bfs()) ans+=dfs(0,inf); printf("%d",sum-ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。