控制棋盘 二分图の最小边覆盖

Description

已知n * m(1<=n,m<=20)的棋盘,其中一些格子有障碍物。现要在棋盘上无障碍物的格子中布置一些马,每只马可以控制两个格子:一个是它所在的格子,另一个是它通过一步可以跳到的格子。马走“日”,所以一步可以跳到8个位置,问你至少要放多少只马才能将所有无障碍物的格子控制?

Input

第1行是两个整数n, m。(1≤n, m≤20) 接下来每行包含两个整数x, y。表示x行y列的格子中有障碍物。

Output

只有一个整数r,即所需要的最少马数。

Sample Input

3 3 2 2

Sample Output

4

喰屎啦坑爹描述喰屎啦坑爹样例!!!!!!!!!!

要是原题里也像我这么加粗的话我就不会WA INF次了...

给你一个棋盘,棋盘上有一些坏了不能放子的格子,现在你有一堆马(就是中国象棋里面那种马),每个马除了本身以外还可以控制他能走到的1个格子,求最少多少马可以控制整个棋盘.
本zz一开始以为一匹马威风八面能走到的地方都直接控制了...那一瞅就是个二分图啊对不对...二分图最小点覆盖对不对...就是最大匹配啊对不对...
WA的一声哭了出来...
事实上这个东西叫做二分图最小边覆盖.建图方法一样,但答案是总点数减去最大匹配数.直接贴代码了...

CQzhangyu ororzzz 大师一眼就看透了一切拯救我于无尽的苦难中%%%%%

dalao之博客

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
using namespace std;
int s,t;
int tot=1,to[N<<5],next[N<<5],head[N],f[N<<5];
void add(int x,int y,int z)
{
	to[++tot]=y;
	f[tot]=z;
	next[tot]=head[x];
	head[x]=tot;
	to[++tot]=x;
	f[tot]=0;
	next[tot]=head[y];
	head[y]=tot;
}
int n,m;
bool map[233][233];
int p(int i,int j)
{
	return (i-1)*m+j;
}
int dx[]={-2,-2,2,2,-1,-1,1,1};
int dy[]={-1,1,-1,1,-2,2,-2,2};
int dis[2333];
bool bfs()
{
	queue<int>q;
	while(!q.empty())q.pop();
	memset(dis,-1,sizeof(dis));
	q.push(s),dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=next[i])if(f[i]>0&&dis[to[i]]<0)
		{
			dis[to[i]]=dis[x]+1;
			q.push(to[i]);
			if(to[i]==t)return true;
		}
	}
	return false;
}
int dinic(int x,int flow)
{
	int a,temp=flow;
	if(x==t)return flow;
	for(int i=head[x];i;i=next[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
	{
		a=dinic(to[i],min(temp,f[i]));
		if(a==0)dis[to[i]]=-1;
		temp-=a;
		f[i]-=a;
		f[i^1]+=a;
		if(temp<=0)break;
	}
	return flow-temp;
}
int maxflow()
{
	int ans=0;
	while(bfs())ans+=dinic(s,1<<30);
	return ans;
}
bool check(int i,int j){return i>0&&i<=n&&j>0&&j<=m;}
int main()
{
	cin>>n>>m;
	s=0,t=n*m+1;
	int x,y,num=0;
	while(scanf("%d%d",&x,&y)!=EOF)map[x][y]=true,num++;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)if(!map[i][j])
		{
			if((i&1)^(j&1))
			{
				add(s,p(i,j),1);
				for(int k=0;k<8;k++)if(check(i+dx[k],j+dy[k])&&(!map[i+dx[k]][j+dy[k]]))
				{
					add(p(i,j),p(i+dx[k],j+dy[k]),1);
				}
			}
			else add(p(i,j),t,1);
		}
	}
	cout<<n*m-num-maxflow();
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注