Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/12
09:46
二分图匹配 最大流

[bzoj 4554] Tjoi2016&Heoi2016 游戏

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

在2016年,佳缘姐姐喜欢上了一款游戏,叫做泡泡堂。简单的说,这个游戏就是在一张地图上放上若干个炸弹,看是否能炸到对手,或者躲开对手的炸弹。在玩游戏的过程中,小H想到了这样一个问题:当给定一张地图,在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列,炸弹的威力可以穿透软石头,但是不能穿透硬石头。给定一张n*m的网格地图:其中*代表空地,炸弹的威力可以穿透,可以在空地上放置一枚炸弹。x代表软石头,炸弹的威力可以穿透,不能在此放置炸弹。#代表硬石头,炸弹的威力是不能穿透的,不能在此放置炸弹。例如:给出1*4的网格地图*xx*,这个地图上最多只能放置一个炸弹。给出另一个1*4的网格地图*x#*,这个地图最多能放置两个炸弹。现在小H任意给出一张n*m的网格地图,问你最多能放置多少炸弹

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行输入两个正整数n,m,n表示地图的行数,m表示地图的列数。1≤n,m≤50。接下来输入n行m列个字符,代表网格地图。*的个数不超过n*m个

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一个整数a,表示最多能放置炸弹的个数

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4 4
#∗∗∗
∗#∗∗
∗∗#∗
xxx#

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

5

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

如果没有#的话就是经典的二分图匹配问题 对于一个可放置的点(i,j),从第i行向第j列连边最后求最大匹配,有了#的话就是把行或者列拆分就可以了

pascal:

c++:

 

[bzoj 4554] Tjoi2016&Heoi2016 游戏