二分图行列匹配---> hdu2119,hdu1498

hdu2119

题意：给定一个矩形方格，每个格子里面的数字是0或者1，每次操作可以把一整行或列的1变成0，问最少多少次操作能将1全部变为0

一次可以消除某一行或者某一列的1
但是可以这么想，最多有多少个1即不在同一行，也不在同一列，有多少个，那么就要消多少次
那么就是求行和列的最大匹配

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 100 + 10;
 4 int Map[N][N];
 5 bool vis[N];
 6 int cy[N];
 7 int n,m;
 8 bool dfs(int u)
 9 {
10     for(int i=0; i<m; ++i)
11     {
12         if(!vis[i] && Map[u][i])
13         {
14             vis[i] = true;
15             if(cy[i] == -1 || dfs(cy[i]))
16             {
17                 cy[i] = u;
18                 return true;
19             }
20         }
21     }
22     return false;
23 }
24 int MaxMatch()
25 {
26     memset(cy, -1, sizeof(cy));
27     int ans = 0;
28     for(int i=0; i<n; ++i)
29     {
30         memset(vis, 0, sizeof(vis));
31         ans += dfs(i);
32     }
33     return ans;
34 }
35 int main()
36 {
37     int i,j;
38     while(true)
39     {
40         scanf("%d",&n);
41         if(n == 0)
42             break;
43         scanf("%d",&m);
44         for(i=0; i<n; ++i)
45             for(j=0; j<m; ++j)
46             {
47                 scanf("%d",&Map[i][j]);
48             }
49         int ans = MaxMatch();
50         printf("%d
",ans);
51     }
52 }

hdu1498

比上面那题复杂一点，不过也是一样，每次只能消一行或者一列相同颜色的气球

一共就50中颜色，我们可以枚举每一种颜色构成的矩形，然后对其进行行列匹配，如果最大匹配 > k , 那么就不能在k次内完全消除该种颜色的气球

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <vector>
 4 using namespace std;
 5 const int N = 100 + 10;
 6 const int M = 50 + 10;
 7 int Map[M][N][N];
 8 int color[M];
 9 bool vis[N];
10 int cy[N];
11 int ans[M];
12 vector<int> G[N];
13 int cnt;
14 int n,k;
15 void init()
16 {
17     for(int i=0; i<n; ++i)
18         G[i].clear();
19     
20 }
21 bool dfs(int u)
22 {
23     for(int i=0; i<G[u].size(); ++i)
24     {
25         int v = G[u][i];
26         if(!vis[v])
27         {
28             vis[v] = true;
29             if(cy[v] == -1||dfs(cy[v]))
30             {
31                 cy[v] = u;
32                 return true;
33             }
34         }
35     }
36     return false;
37 }
38 int MaxMatch()
39 {
40     memset(cy, -1, sizeof(cy));
41     int cnt = 0;
42     for(int i=0; i<n; ++i)
43     {
44         memset(vis, 0, sizeof(vis));
45         cnt += dfs(i);
46     }
47     return cnt;
48 }
49 int main()
50 {
51     //freopen("in.txt","r",stdin);
52     int i,j;
53     while(true)
54     {
55         scanf("%d%d",&n,&k);
56         if(n == 0 && k==0)
57             break;
58         int t;
59         memset(Map, 0, sizeof(Map));
60         memset(color, 0, sizeof(color));
61         cnt = 0;
62         for(i=0; i<n; ++i)
63             for(j=0; j<n; ++j)
64             {
65                 scanf("%d",&t);
66                 Map[t][i][j] = 1;
67                 color[t] = 1;
68             }
69         for(t=1; t<=50; ++t)
70             if(color[t])//枚举每一种颜色构成的矩阵
71             {
72                 init();    
73                 for(i=0; i<n; ++i)
74                     for(j=0; j<n; ++j)
75                     {
76                         if(Map[t][i][j] == 1)
77                             G[i].push_back(j);//用vector存储
78                     }
79                 int tmp = MaxMatch();
80                 if(tmp > k)
81                     ans[cnt++] = t;
82             }
83         if(cnt == 0)
84             puts("-1");
85         else
86         {
87             printf("%d",ans[0]);
88             for(i=1; i<cnt; ++i)
89                 printf(" %d",ans[i]);
90             puts("");
91         }
92     }
93     return 0;    
94 }