hdu 1281 二分图最大匹配

很容易想到是最大匹配：行和列看做点，每一个可放置的位置看做边，先求一遍最大匹配，然后枚举删除每一条边，如果删除了某一条边发现求出来的最大匹配比之前少，则这条边对应的格点是”重要点“。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 101;
 7 bool mp[N][N];
 8 int mark[N];
 9 bool visit[N];
10 int n, m, k;
11 
12 int dfs( int u )
13 {
14     for ( int i = 1; i <= m; i++ )
15     {
16         if ( !visit[i] && mp[u][i] )
17         {
18             visit[i] = 1;
19             if ( mark[i] == -1 || dfs(mark[i]) )
20             {
21                 mark[i] = u;
22                 return 1;
23             }
24         }
25     }
26     return 0;
27 }
28 
29 inline int hungary()
30 {
31     int res = 0;
32     memset( mark, -1, sizeof(mark) );
33     for ( int i = 1; i <= n; i++ )
34     {
35         memset( visit, 0, sizeof(visit) );
36         res += dfs(i);
37     }
38     return res;
39 }
40 
41 int main()
42 {
43     int _case = 1;
44     while ( scanf("%d%d%d", &n, &m, &k) != EOF )
45     {
46         memset( mp, 0, sizeof(mp) );
47         while ( k-- )
48         {
49             int x, y;
50             scanf("%d%d", &x, &y);
51             mp[x][y] = 1;
52         }
53         int cnt = 0, ans = hungary();
54         for ( int i = 1; i <= n; i++ )
55         {
56             for ( int j = 1; j <= m; j++ )
57             {
58                 if ( !mp[i][j] ) continue;
59                 mp[i][j] = 0;
60                 if ( hungary() < ans ) cnt++;
61                 mp[i][j] = 1;
62             }
63         }
64         printf("Board %d have %d important blanks for %d chessmen.
", _case++, cnt, ans);
65     }
66     return 0;
67 }