HDU1498 50 years, 50 colors

　　这题与HDU1281类似，都是行列最大匹配。

　　这题说准确一点儿时求最小点集覆盖，枚举每种颜色，如果当前颜色的最小点集覆盖大于k，那么k次选择都不可能把该种颜色完全消灭。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <vector>
 4 using namespace std;
 5 
 6 const int maxn = 100 + 5;
 7 int n, k;
 8 bool vis[maxn];
 9 int link[maxn];
10 int g[maxn][maxn];
11 
12 bool find(int i, int j)
13 {
14     for(int p = 1; p <= n; p ++)
15     {
16         if(g[i][p] == j && !vis[p])
17         {
18             vis[p] = true;
19             if(!link[p] || find(link[p], j))
20             {
21                 link[p] = i;
22                 return true;
23             }
24         }
25     }
26     return false;
27 }
28 
29 int main()
30 {
31     vector<int> vt;
32     while(scanf("%d%d", &n, &k) == 2 && n + k)
33     {
34         vt.clear();
35         for(int i = 1; i <= n; i ++)
36         for(int j = 1; j <= n; j ++)
37             scanf("%d", &g[i][j]);
38         int cnt;
39         for(int i = 1; i <= 50; i ++)
40         {
41             cnt = 0;
42             memset(link, 0, sizeof link);
43             for(int j = 1; j <= n; j ++)
44             {
45                 memset(vis, 0, sizeof vis);
46                 cnt += find(j, i);
47             }
48             if(cnt > k)
49                 vt.push_back(i);
50         }
51         int size = vt.size();
52         if(size == 0)
53             puts("-1");
54         else
55         {
56             printf("%d", vt[0]);
57             for(int i = 1; i < size; i++)
58                 printf(" %d", vt[i]);
59             putchar('\n');
60         }
61     }
62     return 0;
63 }