【二分图匹配】宫廷守卫
暂无测试数据。
题目描述
从前有一个王国，这个王国的城堡是一个矩形，被分为M×N个方格。一些方格是墙，而另一些是空地。这个王国的国王在城堡里设了一些陷阱，每个陷阱占据一块空地。
一天，国王决定在城堡里布置守卫，他希望安排尽量多的守卫。守卫们都是经过严格训练的，所以一旦他们发现同行或同列中有人的话，他们立即向那人射击。因此，国王希望能够合理地布置守卫，使他们互相之间不能看见，这样他们就不可能互相射击了。守卫们只能被布置在空地上，不能被布置在陷阱或墙上，且一块空地只能布置一个守卫。如果两个守卫在同一行或同一列，并且他们之间没有墙的话，他们就能互相看见。(守卫就像象棋里的车一样)
你的任务是写一个程序，根据给定的城堡，计算最多可布置多少个守卫，并设计出布置的方案。
Format
输入格式：
第一行两个整数M和N(1≤M，N≤200)，表示城堡的规模。
接下来M行N列的整数，描述的是城堡的地形。第i行j列的数用ai,j表示。
ai,j=0，表示方格[i,j]是一块空地；
ai,j=1，表示方格[i,j]是一个陷阱；
ai,j=2，表示方格[i,j]是墙。
输出格式：
第一行一个整数K，表示最多可布置K个守卫。
Sample 1
Input
3 4
2 0 0 0
2 2 2 1
0 1 0 2
Output
2
Limitation
10s, 65536KiB for each test case.
Hint
【算法分析】
本题的关键在构图。
城堡其实就是一个棋盘。我们把棋盘上横向和纵向连续的极长段（不含墙）都分离出来。显然，每一段上最多只能放一个guard，而且guard总是放在一个纵向段和一个横向段的交界处，所以一个guard和一个纵向段和一个横向段有关。
我们把纵向段和横向段都抽象成图中的节点，如果一个纵向段和一个横向段相交的话，就在两点之间连一条边。这样，guard就成为了图中的边。前面得出的性质抽象成图的语言就是，每个点只能和一条边相连，每条边只能连接一个纵向边的点和一个横向边的点。因此，这样的图是二分图，我们所求的正是二分图的匹配。而要布置最多的guards，就是匹配数要最大，即最大匹配。
图中节点数为n（n≤200），求最大匹配的时间复杂度为O(n^2.5)。
