【二分图匹配-最小边覆盖】mz语考试

Description
jswf夺冠后
cc: tql
gj: tggl
mz:tlrxml
frz: bksjs
wjjj: whnzmqa
......
js: ??? 
js: nmflb

————节选自某次mz语等级测试

mz语等级测试即将到来。然而mz语十分难,用词灵活多变,导致作弊人数众多。而防止考生作弊的一个有效的途径是让考生之间保持一定的距离。

某考场有R(行)*C(列)个座位,坐在(r, c)的考生可能会看到(r,c-1)、(r,c+1)、(r-1,c-1)、(r-1,c+1)(即左、右、左前、右前)4个位置的考生的答案。

为了防止这种情况发生,就要保证一个考生周围的这4个位置中无其他考生。

而由于这个考场年久失修,有一些座位已经损坏,是无法使用的。

现在,fls想知道,在保证无人能看到别人答案的前提下,这个考场最多能安排多少名考生?

Input
多组数据

第一行有一个整数T(T<=30),代表数据组数。

对每组数据,第一行有两个整数R、C(1 <= R, C <= 50),表示考场规模。

接下来R行,每行有一个长度为C的字符串,描述考场内每个位置。'.'表示该位置可用,'x'则表示已损坏。

Output
对每组数据,输出该考场内最多能安排的考生数。

Sample Input
1
2 3
...
.x.
Sample Output
4

相隔两列的人是看不见对方的。所以把有冲突的座位连边即为二分图。

任意两个冲突的位置只能有一个地方坐人,即任意点只能有一条边相连。边数就是能坐下的人。转化为了最小边覆盖问题。

答案就是 点数-最大匹配数

注意link vis这些变量名有可能会与STL冲突

#include<vector>
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string> 
using namespace std;
int dx[]={-1, 0, 1,-1,0,1};
int dy[]={-1,-1,-1, 1,1,1};
char tsr[55][55];
vector<int> G[3025];
int id[55][55];
int visa[3025]={0};
int linka[3025]={0};
int r,c;
int lig(int x,int y)
{
	return x<=r&&x>=0&&y<=c&&y>=0;
}
int hung(int x)
{
	int v;
	for(int i=0;i<G[x].size();i++)
	{
		v=G[x][i];
		if(visa[v]) continue;
		visa[v]=1;
		if(linka[v]==0||hung(linka[v]))
		{
			linka[v]=x;
			return 1;
		}
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(linka,0,sizeof(linka));
		memset(id,0,sizeof(id));
		int cnt1=0,cnt2=0;
		scanf("%d%d",&r,&c);
		for(int i=1;i<=r;i++) scanf("%s",tsr[i]+1);
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j++)
			{
				if(tsr[i][j]!='.') continue;
				if(j&1) id[i][j]=++cnt1;
				else id[i][j]=++cnt2;
			}
		}
		for(int i=1;i<=cnt1;i++) G[i].clear();
		for(int i=1;i<=r;i++)
		{
			for(int j=1;j<=c;j+=2)
			{
				if(tsr[i][j]!='.') continue;
				for(int k=0;k<6;k++)
				{
					int x=i+dx[k],y=j+dy[k];
					if(tsr[x][y]=='.' && lig(x,y))
					{
						G[id[i][j]].push_back(id[x][y]);
					}
				}
			}
		}
		int ans=0;
		for(int i=1;i<=cnt1;i++)
		{
			memset(visa,0,sizeof(visa));
			ans+=hung(i);
		}
		printf("%d\n",cnt1+cnt2-ans);
	}
}

 

发表评论

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