[ HDU - 1045 1245 ] 二分图匹配

HDU - 1045 Fire Net

题意：\(n\ast n\)的矩阵，内有墙和被标记格。被标记格的上下左右方向射线上都不能有其他标记格，除非中间有墙阻隔。给定墙的位置，问最多可以标记多少个格子？

题解：

按行列建二分图，对于一行，按连续的空位对矩阵宽缩点。对于一列，按连续的空位对矩阵高缩点。并建立各点间的连接。然后直接跑二分图匹配即可。

题意：\(n\ast m\)的矩阵，内有部分格子可以放棋子，其他不能。问重要点（即如果该点不能放棋子则放入车的最大个数减少）的个数有多少个？

题解：和上一题不同的是，上一题有墙，他不仅不可以放，也不能被射穿，但是这里是可以"射穿"的。所以老老实实只按行列建图，计算二分图最大匹配，然后对所有可以放棋子的点逐个遍历并修改为不可放置的点，重新计算二分图最大匹配，比对之前答案有无减少，若有减少则重要点计数+1.

图论-二分图