二分图行列匹配与最大匹配必须边

hdu1287

题意：在棋盘上放置车，要求车不能相互攻击，即要求车要在不同的行和列，二分图行列匹配

但是又问，那些点如果不放置车，就不能形成最大匹配，即哪些边是最大匹配的必须边

判断是否是最大匹配的必须边，只要删除该边之后做匹配，将匹配的个数与原先的个数比较就知道该边是不是最大匹配的必须边

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100 + 10;
 4 int Map[N][N];
 5 int n,m,k;
 6 bool vis[N];
 7 int cy[N],cx[N];
 8 
 9 bool dfs(int u)
10 {
11     for(int i=0; i<m; ++i)
12     {
13         if(!vis[i] && Map[u][i]==1)
14         {
15             vis[i] = true;
16             if(cy[i]==-1 || dfs(cy[i]))
17             {
18                 cy[i] = u;
19                 cx[u] = i;
20                 return true;
21             }
22         }
23     }
24     return false;
25 }
26 int MaxMatch()
27 {
28     memset(cx, -1, sizeof(cx));
29     memset(cy, -1, sizeof(cy));
30     int cnt = 0;
31     for(int i=0; i<n; ++i)
32     {
33         if(cx[i] == -1)
34         {
35             memset(vis, 0, sizeof(vis));
36             cnt += dfs(i);
37         }
38     }
39     return cnt;
40 }
41 int main()
42 {
43     int i,j,x,y;
44     int tCase = 1;
45     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
46     {
47         memset(Map, 0, sizeof(Map));
48         for(i=0; i<k; ++i)
49         {
50             scanf("%d%d",&x,&y);
51             x-=1;y-=1;
52             Map[x][y] = 1;
53         }
54         int ans = MaxMatch();
55         int ans2 = 0;
56         for(i=0; i<n; ++i)
57             for(j=0; j<m; ++j)
58                 if(Map[i][j] == 1)
59                 {
60                     Map[i][j] = 0;//删边
61                     int cnt = MaxMatch();
62                     if(cnt != ans)
63                         ans2++;
64                     Map[i][j] = 1;
65                 }
66         printf("Board %d have %d important blanks for %d chessmen.
",tCase++,ans2,ans);
67     }
68     return 0;
69 }