【CH6901】骑士放置

题目大意：给定一个 N*M 的棋盘，有一些格子禁止放棋子。问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。N, M<=100。

题解：相同的道理，放置一个马就在两个点之间连一条边。求的是二分图的最大独立集，即：二分图点数减去最小点覆盖数即可。

代码如下

#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={2,2,-2,-2,1,1,-1,-1};

const int dy[]={1,-1,1,-1,2,-2,2,-2};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const int maxn=1e4+10;

const double eps=1e-6;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll read(){

	ll x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

/*--------------------------------------------------------*/

vector<int> G[maxn];

int match[maxn];bool vis[maxn];

int n,m,t;

bool mpp[101][101];

inline int get(int i,int j){return m*(i-1)+j;}

inline bool right(int i,int j){return i>=1&&i<=n&&j>=1&&j<=m&&!mpp[i][j];}

void read_and_parse(){

	n=read(),m=read(),t=read();

	for(int i=1,x,y;i<=t;i++)x=read(),y=read(),mpp[x][y]=1;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)if(!mpp[i][j]&&!((i+j)&1))

			for(int k=0;k<8;k++)

				if(right(i+dx[k],j+dy[k])){

					int x=get(i,j),y=get(i+dx[k],j+dy[k]);

					G[x].pb(y);

				}

}

bool dfs(int u){

	for(auto v:G[u])if(!vis[v]){

		vis[v]=1;

		if(!match[v]||dfs(match[v])){

			match[v]=u;return 1;

		}

	}

	return 0;

}

void solve(){

	int ans=n*m-t;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++){

			if(((i+j)&1)||mpp[i][j])continue;

			memset(vis,0,sizeof(vis));

			if(dfs(get(i,j)))--ans;

		}

	printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【CH6901】骑士放置

最新文章

热门文章