hdu 1498 50 years, 50 colors（二分匹配，最小点覆盖）

用户1624346

发布于 2018-04-17 16:03:53

4930

发布于 2018-04-17 16:03:53

文章被收录于专栏：calmound

题意：n*n的矩阵放置不同的颜色（不同的数字代表不同的颜色），你有k次选择，每一次只能选择某一行或某一列，可以消除该行（列）的所有颜色，问有哪几种颜色，无论怎样经过k次选择后依然无法完全抹去。

分析：依旧是将横坐标作为x集，纵坐标作为y集合进行匹配。对于某种颜色的匹配，如果他的最大匹配大于k，则该颜色在k次里无论如何都无法抹去的。

还有一个问题就是为什么这道题是最小点覆盖，通过自己画图就知道了

假设x｛1｝和｛1，2，3，4｝分别连接，x｛2｝和y｛3｝连接，则只用选择1，2行，就可以将所有的颜色抹去了

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int MAXN=150;
 6 int map[MAXN][MAXN];
 7 int pre[MAXN];
 8 int vis[MAXN];
 9 int used[MAXN];
10 int ans[MAXN];
11 int n,k;
12 
13 bool cmp(int a,int b)
14 {
15     return a<b;
16 }
17 
18 int find(int cur,int color)
19 {
20     int i;
21     for(i=1; i<=n; i++)
22     {
23         if(map[cur][i]==color && !vis[i])//对应的某一列是否存在该color
24         {
25             vis[i]=1;
26             if(pre[i]==-1 || find(pre[i],color))//这里find的是pre【i】，刚开始这里敲错了wa了两次
27             {
28                 pre[i]=cur;
29                 return 1;
30             }
31         }
32     }
33     return 0;
34 }
35 
36 int main()
37 {
38     int i,j,t,w,sum;
39     int len;
40     while(scanf("%d%d",&n,&k))
41     {
42         if(n==0 && k==0) break;
43         memset(map,0,sizeof(map));
44         memset(used,0,sizeof(used));
45 
46         for(i=1; i<=n; i++)
47         {
48             for(j=1; j<=n; j++)
49             {
50                 scanf("%d",&w);
51                 map[i][j]=w;
52             }
53         }
54         len=0;
55         for(i=1; i<=n; i++)
56         {
57             for(j=1; j<=n; j++)
58             {
59                 memset(pre,-1,sizeof(pre));
60                 sum=0;
61                 if(used[map[i][j]]==0)//该颜色没有出现过
62                 {
63                     used[map[i][j]]=1;
64                     for(t=1; t<=n; t++)//枚举每一行
65                     {
66                         memset(vis,0,sizeof(vis));
67                         sum+=find(t,map[i][j]);
68                     }
69                 }
70                 if(sum>k) ans[len++]=map[i][j];
71             }
72         }
73         if(len==0) printf("-1\n");
74         else
75         {
76             sort(ans,ans+len,cmp);
77             for(i=0;i<len;i++)
78             {
79                 if(i) printf(" ");
80                 printf("%d",ans[i]);
81             }
82             printf("\n");
83         }
84     }
85 }

set容器

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<set>
 4 #include<algorithm>
 5 #include<iostream>
 6 using namespace std;
 7 
 8 const int MAXN=150;
 9 
10 set<int>s;
11 int map[MAXN][MAXN];
12 int pre[MAXN];
13 int vis[MAXN];
14 int used[MAXN];
15 int ans[MAXN];
16 int n,k;
17 
18 int find(int cur,int color)
19 {
20     int i;
21     for(i=1; i<=n; i++)
22     {
23         if(map[cur][i]==color && !vis[i])
24         {
25             vis[i]=1;
26             if(pre[i]==-1 || find(pre[i],color))
27             {
28                 pre[i]=cur;
29                 return 1;
30             }
31         }
32     }
33     return 0;
34 }
35 
36 int main()
37 {
38     int i,j,t,w,sum;
39     int len;
40     while(scanf("%d%d",&n,&k))
41     {
42         s.clear();
43         if(n==0 && k==0) break;
44         memset(map,0,sizeof(map));
45 
46         for(i=1; i<=n; i++)
47         {
48             for(j=1; j<=n; j++)
49             {
50                 scanf("%d",&w);
51                 s.insert(w);
52                 map[i][j]=w;
53             }
54         }
55         len=0;
56         sum=0;
57         set<int>::iterator iter;
58         for(iter=s.begin(); iter!=s.end(); iter++)
59         {
60             //cout<<"值"<<*iter<<endl;
61             memset(pre,-1,sizeof(pre));
62             sum=0;//这里忘记了
63             for(t=1; t<=n; t++)
64             {
65                 memset(vis,0,sizeof(vis));
66                 sum+=find(t,*iter);
67             }
68             if(sum>k) ans[len++]=*iter;
69         }
70         if(len==0) printf("-1\n");
71         else
72         {
73             for(i=0; i<len; i++)
74             {
75                 if(i) printf(" ");
76                 printf("%d",ans[i]);
77             }
78             printf("\n");
79         }
80     }
81 }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2013-01-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法