D棋盘游戏（二分匹配）

D-棋盘游戏小希和Gardon在玩一个游戏对一个N*M的棋盘在格子里放尽量多的一些国际象棋里面的“车”并且使得他们不能互相攻击对一个N*M的棋盘在格子里放尽量多的一些国际象棋里面的“车”并且使得他们不能互相攻击这当然很简单但是Gardon限制了只有某些格子才可以放小希还是很轻松的解决了这个问题见下图注意不能放车的地方不影响车的互相攻击。 所以现在Gardon想让小希来解决一个更难的问题在保证尽量多的“车”的前提下棋盘里有些格子是可以避开的也就是说不在这些格子上放车也可以保证尽量多的“车”被放下。但是某些格子若不放子就无法保证放尽量多的“车”这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点你能解决这个问题么

Input

输入包含多组数据 第一行有三个数N、M、K(1

Output

对输入的每组数据按照如下格式输出 Board T have C important blanks for L chessmen.

Sample Input

3 3 41 21 32 12 23 3 41 21 32 13 2

Sample Output

Board 1 have 0 important blanks for 2 chessmen.Board 2 have 3 important blanks for 3 chessmen .

题意 

           T 是 第几组数据。C 是重要点的个数L 是最多放棋子的个数。

思路  

          把 x当作左边的点把y当作右边的点进行 最大匹配得 L的个数。

  然后 把  所给的能放棋子的点 删掉 再求 最大匹配如果小于先前所求最大匹配那么就是重要点。

 代码

        

#include#include#include#include#include#include#includeusing namespace std;#define mem(a,b) memset(a,b,sizeof(a))#define MM 120int line[MM][MM],book[MM],man[MM]; int n,m,imp0; //imp重要点个数struct zaq{int x,y;}qq[MM*MM];bool Find(int x){for(int i1;i