很简单的求最小点覆盖、
code:
#include <set> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 110; int n,k; set<int> col; set<int>::iterator it; int ans[MAXN],cnt; bool graph[MAXN][MAXN]; bool vis[MAXN]; int link[MAXN],a[MAXN][MAXN]; int find(int x) { int y; for(y=1;y<=n;y++) { if(graph[x][y] && !vis[y]) { vis[y]=true; if(!link[y] || find(link[y])) { link[y]=x; return true; } } } return false; } int solve() { int x,num=0; for(x=1;x<=n;x++) { memset(vis,0,sizeof(vis)); if(find(x)) num++; } return num; } int main() { int i,j; while(~scanf("%d%d",&n,&k) && (n+k)) { col.clear(); cnt=0; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { scanf("%d",&a[i][j]); col.insert(a[i][j]); } } for(it=col.begin();it!=col.end();it++) { memset(link,0,sizeof(link)); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[i][j]==(*it)) { graph[i][j]=1; }else{ graph[i][j]=0; } } } int t=solve(); if(t>k) { ans[++cnt]=(*it); //printf("max:%d col:%d \n",t,*it); } } if(!cnt) puts("-1"); else{ for(i=1;i<cnt;i++) printf("%d ",ans[i]); printf("%d\n",ans[cnt]); } } return 0; }