首页 > 代码库 > hdu1498 50 years, 50 colors --- 最小点覆盖
hdu1498 50 years, 50 colors --- 最小点覆盖
给一个矩阵,里面有一些不同颜色的气球,每次可以消灭一行或一列中某一种颜色的气球,问你在k次及以内,有哪些颜色的气球是无论如何也消不完的。
那么思路就是,对每一种颜色的气球求最小点覆盖,>k 则为答案。
相当于 poj3041 的加强版,因为矩阵中不是每一个点都是等价的。
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> const int maxn=105; using namespace std; int mx[maxn],my[maxn],vis[maxn],e[maxn][maxn],n,cnt,mp[maxn][maxn],mat[maxn],ans[maxn]; map<int,int> mmp; int path(int i) { int j; for(j=0;j<n;j++) { if(e[i][j]&&!vis[j]) { vis[j]=1; if(my[j]==-1||path(my[j])) { mx[i]=j; my[j]=i; return 1; } } } return 0; } int hungry() { int res=0; memset(mx,-1,sizeof mx); memset(my,-1,sizeof my); for(int i=0;i<n;i++) { if(mx[i]==-1) { memset(vis,0,sizeof vis); res+=path(i); } } return res; } int main() { int k,i,j,m,p,x; while(scanf("%d%d",&n,&k)&&(n||k)) { cnt=1; mmp.clear(); for(i=0;i<n;i++) for(j=0;j<n;j++) { scanf("%d",&mp[i][j]); if(mmp[mp[i][j]]) continue; else { mmp[mp[i][j]]=cnt; mat[cnt++]=mp[i][j]; } } m=0; for(p=1;p<cnt;p++) { x=mat[p]; memset(e,0,sizeof e); for(i=0;i<n;i++) for(j=0;j<n;j++) if(mp[i][j]==x) e[i][j]=1; if(hungry()>k) ans[m++]=x; } if(m==0) printf("-1\n"); else { sort(ans,ans+m);//wa了一次。。 printf("%d",ans[0]); for(i=1;i<m;i++) printf(" %d",ans[i]); puts(""); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。