HDU 1498 50 years, 50 colors

时间：2014-03-31 12:00:34 收藏：0 阅读：536

题目大意：给你一个 n*n 的矩阵，每个格子上对应着相应颜色的气球，每次你可以选择一行或一列的同种颜色的气球进行踩破，问你在K次这样的操作后，哪些颜色的气球是不可能被踩破完的。

题解：对于每一种颜色建图，对于每一个点，要么横坐标被染色，要么纵坐标被染色，所以就是最小点覆盖。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using 
namespace std;
const 
int N=105;
int k,m,n;
int ans[55],link[N],used[N];
int map[N][N];
bool 
vis[N];
vector v[N];
bool 
Dfs(int 
k){
    for(int 
i=0;i<v[k].size();i++){
        int 
a=v[k][i];
        if(used[a]==0){
            used[a]=1;
            if(link[a]==-1||Dfs(link[a])){link[a]=k;return 
1;}
        }
    }return 
0;
}
int 
main(){
    while(scanf("%d%d",&n,&k),n!=0&&k!=0){
        for(int 
i=1;i<=n;i++)
          for(int 
j=1;j<=n;j++)scanf("%d",&map[i][j]);
          memset(vis,false,sizeof(vis));int 
cnt=0;
        for(int 
i=1;i<=n;i++)for(int 
j=1;j<=n;j++)
        if(!vis[map[i][j]]){
            vis[map[i][j]]=true;
            for(int 
t=0;t<N;t++)v[t].clear();
            for(int 
t=1;t<=n;t++)
              for(int 
u=1;u<=n;u++)
              if(map[t][u]==map[i][j])v[t].push_back(u);
              int 
count=0; memset(link,-1,sizeof(link));
            for(int 
u=1;u<=n;u++){
                memset(used,0,sizeof(used));
                if(Dfs(u))count++;
            }
            if(count>k)ans[cnt++]=map[i][j];
        }
        if(cnt==0)puts("-1");
        else{
            sort(ans,ans+cnt);
            for(int 
i=0;i<cnt-1;i++)printf("%d ",ans[i]);
            printf("%d\n",ans[cnt-1]);
        }
    }
    return 
0;
}

HDU 1498 50 years, 50 colors,布布扣,bubuko.com

原文：http://www.cnblogs.com/forever97/p/3633808.html