题解 P2825 【[HEOI2016/TJOI2016]游戏】
[P2825][HEOI2016/TJOI2016]游戏
Algorithm: 匈牙利算法, 图论建模
Created: Aug 10, 2020 7:07 PM
Difficulty: 省选/NOI-
URL: https://www.luogu.com.cn/problem/P2825
画外音：在调试时我是这个表情： ????；AC了这题时我是这个表情： ????；看到这题的题解还没满时我是这个表情： ????
题目链接：
[HEOI2016/TJOI2016]游戏
「TJOI / HEOI2016」游戏 - 题目 - LibreOJ
题解：
在做这题前，你（不）需要先AC这题并且熟练掌握匈牙利算法求二分图的最大匹配：
[ZJOI2007]矩阵游戏
首先观察一下题目，若是把硬石子全部当成软石子，就可以将题意转换成：“每摆放一个炸弹，它所在的行和列都不再能摆放其它的棋子，其中本身就有一些点是不可以摆放炸弹的。”是不是很简单？将行看成集合
加了硬石子，又怎么做？
我们可以从二分图的本质考虑起。二分图重在同一集合内部元素不相交，不同集合元素有相连边。那么此时，如果一行内存在一个硬石子，这一行就会被分成不相交的两部分。如果把这两部分都看成一个独立的行，此时，行与行仍然不相交，列与行仍然会相交，满足二分图的性质，那么，此方案可行。
拿样例举个例子吧：
#***
*#**
**#*
xxx#原来的矩阵长这样
#111
2#22
33#3
xxx#如果将硬石子看成软石子，我们会这样给每行中可以放炸弹的节点编号
#111
2#33
44#5
xxx#但是硬石子将每行划分成了多个单独的行，因此我们要将硬石子后的可放石子的节点所处的行加一。注意：这里的行已经不是原来意义上的行了，这里是被硬石子分割后抽象出来的单独的行
这样，我们就把行的编号处理完了，列的编号也同理。
直接上代码吧，这样方便理解，几个比较坑的点在注释里讲了：
//File: P2825.cpp
//Author: yanyanlongxia
//Date: 2020/8/10
//
#include <bits/stdc++.h>
using namespace std;
int n,m,ntot,mtot,tot,head[3000],nxt[3000],ver[3000],row[60][60],col[60][60],match[3000],ans;
bool vis[3000];
void add(int x,int y)//链式前向星加边
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
bool find(int x)//匈牙利算法
{
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i];
if(!vis[y])
{
vis[y]=true;
if(!match[y] || find(match[y]))
{
match[y]=x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d",&n,&m);
char s[60][60];
bool flag=1;//注意第一次需要单开一行
pair<int,int>last;//与动态规划的思想相似，每个点所在的抽象出的行的编号都可以由上一个有编号的点转移过来
for(int i=1;i<=n;i++)
{
scanf("%s",(s[i]+1));
for(int j=1;j<=m;j++)
{
if(s[i][j]=='#')//下一次另开一行（抽象意义上的行）
{
flag=1;
continue;
}
if(flag==0)//不需要加1
{
if(s[i][j]!='x')
{
row[i][j]=row[last.first][last.second];//row数组的意义为该点所在的抽象的行的编号
last=make_pair(i,j);
}
} else
if(s[i][j]!='x')
{
row[i][j]=row[last.first][last.second]+1;
ntot++;
last=make_pair(i,j);
flag=0;//当前的加处理完毕
}
}
flag=1;//换行一定要加一
}
flag=1;
last=make_pair(0,0);//清零，赋初值
for(int i=1;i<=m;i++)//列的处理，与行相似，但是i与j要取反
{
for(int j=1;j<=n;j++)
{
if(s[j][i]=='#')
{
flag=1;
continue;
}
if(flag==0)
{
if(s[j][i]!='x')
{
col[j][i]=col[last.second][last.first];//col数组与row数组的意义相似，是列的编号
last=make_pair(i,j);
}
} else
if(s[j][i]!='x')
{
col[j][i]=col[last.second][last.first]+1;
mtot++;
last=make_pair(i,j);
flag=0;
}
}
flag=1;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
if (s[i][j]=='*')
add(row[i][j],col[i][j]);//加边
}
for (int i = 1; i <= ntot; ++i) {
memset(vis,0,sizeof(vis));
if(find(i))
ans++;//统计最大匹配
}
printf("%d\n",ans);
return 0;
}