洛谷3355 骑士共存问题

本文主要是介绍洛谷3355 骑士共存问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

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

输出格式：

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

发现格子可以分成黑白两部分，不能共存的连无穷大的边，分别向源、汇连1的边表示舍弃费用，最后求最小割。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int s=50005,t=50006,oo=0x3f3f3f3f;
int xx[8]={-2,-2,-1,-1,1,1,2,2},yy[8]={1,-1,2,-2,2,-2,1,-1},
fir[50010],ne[700010],to[700010],w[700010],f[50010],que[50010],
ban[210][210],
n,m,tot;
void add(int u,int v,int x)
{tot++;ne[tot*2]=fir[u];fir[u]=tot*2;to[tot*2]=v;w[tot*2]=x;ne[tot*2+1]=fir[v];fir[v]=tot*2+1;to[tot*2+1]=u;w[tot*2+1]=0;
}
bool ok(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=n&&!ban[x][y];
}
bool bfs()
{int i,j,hd,tl,u,v;for (i=1;i<=n;i++)for (j=1;j<=n;j++)f[i*n+j]=0;f[t]=0;f[s]=1;hd=tl=1;que[1]=s;while (hd<=tl){u=que[hd++];for (i=fir[u];i;i=ne[i])if (w[i]&&!f[v=to[i]]){f[v]=f[u]+1;que[++tl]=v;}}return f[t];
}
int dfs(int u,int lim)
{int ret=0,i,v,x;if (u==t) return lim;for (i=fir[u];i&&ret<lim;i=ne[i])if (w[i]&&f[v=to[i]]==f[u]+1){x=dfs(v,min(lim-ret,w[i]));ret+=x;w[i]-=x;w[i^1]+=x;}if (!ret) f[u]=0;return ret;
}
int main()
{int i,j,k,x,y,ans;scanf("%d%d",&n,&m);ans=n*n-m;while (m--){scanf("%d%d",&x,&y);ban[x][y]=1;}for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (!ban[i][j]){if (i+j&1){add(s,i*n+j,1);for (k=0;k<8;k++)if (ok(x=i+xx[k],y=j+yy[k]))add(i*n+j,x*n+y,oo);}elseadd(i*n+j,t,1);}while (bfs())while (x=dfs(s,oo))ans-=x;printf("%d\n",ans);
}