[HEOI2016/TJOI2016]游戏 解题报告

[HEOI2016/TJOI2016]游戏

看起来就是个二分图匹配啊

最大化匹配是在最大化边数，那么一条边就代表选中一个坐标内的点

但是每一行不一定只会有一个匹配

于是把点拆开，按照'#'划分一下就好了

---

Code:

#include <cstdio>
#include <cstring>
#include <cctype>
template <class T>
void read(T &x)
{
	x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
const int N=52;
const int M=1010;
int Idr[N][N],Idc[N][N],r,c,n,m,yuu[M][M],vis[M],mat[M];
char s[N][N];
bool dfs(int now)
{
	for(int i=1;i<=m;i++)
		if(!vis[i]&&yuu[now][i])
		{
			vis[i]=1;
			if(!mat[i]||dfs(mat[i]))
				return mat[i]=now,true;
		}
	return false;
}
int main()
{
	read(r),read(c);
	for(int i=1;i<=r;i++)
	{
		scanf("%s",s[i]+1);
		int las=1;
		for(int j=1;j<=c+1;j++)
		{
			if(s[i][j]=='#'||j==c+1)
			{
				if(las==j) {las=j+1;continue;}
				++n;
				for(int k=las;k<j;k++) Idr[i][k]=n;
				las=j+1;
			}
		}
	}
	for(int j=1;j<=c;j++)
	{
		int las=1;
		for(int i=1;i<=r+1;i++)
		{
			if(s[i][j]=='#'||i==r+1)
			{
				if(las==i) {las=i+1;continue;}
				++m;
				for(int k=las;k<i;k++) Idc[k][j]=m;
				las=i+1;
			}
		}
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++)
			if(s[i][j]=='*')
				yuu[Idr[i][j]][Idc[i][j]]=1;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof vis);
		ans+=dfs(i);
	}
	printf("%d
",ans);
	return 0;
}

---

2019.3.6