【bzoj4554】[Tjoi2016&Heoi2016]游戏

现在问题有硬石头和软石头的限制

所以要对地图进行预处理

分行做,把有#隔开的*(x)形成联通块的存储下来。 
分列作,把有#隔开的*(x)形成联通块的存储下来。

求出所有的行联通个数和列联通个数

作为二分图两边的点

求一遍最大匹配

#include<cstdio>
using namespace std; typedef long long LL; #define N 2500 struct edge
{
int to,next;
}e[N];
int head[N];
int cnt; int vis[N],ly[N]; int xx[51][51],yy[51][51]; char ch[51][51]; int n,m;
int k1=1,k2=1;
int ans; void link(int x,int y)
{
e[++cnt]=(edge){y,head[x]};
head[x]=cnt;
} int dfs(int x,int d)
{
for (int i=head[x];i;i=e[i].next)
{
int t=e[i].to;
if (vis[t]==d)
continue;
vis[t]=d;
if (!ly[t] || dfs(ly[t],d))
{
ly[t]=x;
return true;
}
}
return false;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%s",ch[i]+1);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (ch[i][j]=='#')
k1++;
xx[i][j]=k1;
}
k1++;
}
for (int j=1;j<=m;j++)
{
for (int i=1;i<=n;i++)
{
if (ch[i][j]=='#')
k2++;
yy[i][j]=k2;
}
k2++;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (ch[i][j]=='*')
link(xx[i][j],yy[i][j]);
for (int i=1;i<=k1;i++)
ans+=dfs(i,i);
printf("%d\n",ans);
return 0;
}

  

上一篇:【Java每日一题】20161222


下一篇:BZOJ4554: [Tjoi2016&Heoi2016]游戏