hdu 1281 二分图匹配

题目：在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？

二分图匹配居然还能这么用！！！脑洞大开啊！！！

思路：把棋盘的行x看成二分图左边的点，列y看成二分图右边的点，那么就把可以放车的位置看成是一条边，而二分图的最大匹配中x互不相同，y 互不相同，所以每个匹配都是不同行不同列，所以最大匹配就是最多可以放的车的数量。而要判断有多少个点是必须放的，只要在得出最大匹配后，每次去掉一个匹配，再去运算看得出的结果是否与原来的最大匹配数相同，若相同就不是必须的，若不相同就是必须的。

Sample Input

3 3 4　　//棋盘行列，可以放的位置数目
1 2　　　　//位置坐标
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2

Sample Output

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

 1 #include<iostream>
 2 #include<string.h>
 3 #include<vector>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxn = 105;
 7 int uN,vN;//u,v的数目，使用前面必须赋值
 8 int g[maxn][maxn];//邻接矩阵
 9 int linker[maxn];
10 bool used[maxn];
11 bool dfs(int u)
12 {
13     for(int v = 1; v <=vN;v++)  //注意编号
14     if(g[u][v] && !used[v])
15     {
16         used[v] = true;
17         if(linker[v] == -1 || dfs(linker[v]))
18         {
19             linker[v] = u;
20             return true;
21         }
22     }
23     return false;
24 }
25 int hungary()
26 {
27     int res = 0;
28     memset(linker,-1,sizeof(linker));
29     for(int u=1;u <=uN;u++) //注意编号
30     {
31         memset(used,false,sizeof(used));
32         if(dfs(u))res++;
33     }
34     return res;
35 }
36 int main()
37 {
38     int n;
39     int i,j,k;
40     int ccase=0;
41     freopen("1.in","r",stdin);
42     while(scanf("%d%d%d",&uN,&vN,&n)!=EOF)
43     {
44         memset(g,0,sizeof(g));
45         ccase++;
46         int cnt=0;
47         int p,q;
48         for(i=0;i<n;i++)
49         {
50             scanf("%d%d",&p,&q);
51             g[p][q]=1;
52         }
53         int ans=hungary();
54         for(i=1;i<=uN;i++)  //注意编号
55         {
56             for(j=1;j<=vN;j++)
57             {
58                 if(g[i][j]==1)
59                 {
60                     g[i][j]=0;
61                     //printf("%d %d ***%d
",i,j,hungary()  );
62                     if(ans>hungary())   cnt++;
63                     g[i][j]=1;
64                 }
65             }
66         }
67         printf("Board %d have %d important blanks for %d chessmen.
",ccase,cnt,ans);
68     }
69     return 0;
70 }