HDU——T 1498 50 years, 50 colors

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 const int N(110);
 6 bool map[N][N],vis[N],linked[N];
 7 int n,k,col[N][N],ans[N],match[N];
 8 
 9 bool find(int u)
10 {
11     for(int v=1;v<=n;v++)
12         if(map[u][v]&&!vis[v])
13         {
14             vis[v]=1;
15             if(!match[v]||find(match[v]))
16             {
17                 match[v]=u;
18                 return true;
19             }
20         }
21     return false;
22 }
23 bool link()
24 {
25     int ret=0;
26     for(int i=1;i<=n;i++)
27     {
28         if(find(i)) ret++;
29         memset(vis,0,sizeof(vis));
30     }
31     memset(match,0,sizeof(match));
32     return ret>k;
33 }
34 
35 int main()
36 {
37     for(;scanf("%d%d",&n,&k)&&n&&k;)
38     {
39         int cnt=0;
40         for(int i=1;i<=n;i++)
41           for(int j=1;j<=n;j++)
42             scanf("%d",&col[i][j]);
43         for(int i=1;i<=n;i++)
44             for(int j=1;j<=n;j++)
45               {
46                   if(linked[col[i][j]]) continue;
47                   linked[col[i][j]]=true;
48                   for(int u=1;u<=n;u++)
49                       for(int v=1;v<=n;v++)
50                           if(col[u][v]==col[i][j])
51                               map[u][v]=1;
52                   if(link()) ans[++cnt]=col[i][j];
53                   memset(map,0,sizeof(map));
54             }
55         memset(linked,0,sizeof(linked));
56         if(!cnt) puts("-1");
57         else
58         {
59             std:: sort(ans+1,ans+cnt+1);
60             for(int i=1;i<cnt;i++)
61                 printf("%d ",ans[i]);
62             printf("%d\n",ans[cnt]);
63         }
64         memset(ans,0,sizeof(ans));
65     }
66     return 0;
67 }