hdu 1498 50 years, 50 colors（枚举，最小顶点覆盖）

本文链接：https://blog.csdn.net/acm_cxq/article/details/52050290

50 years, 50 colors

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2253 Accepted Submission(s): 1264

Problem Description

On Octorber 21st, HDU 50-year-celebration, 50-color balloons floating around the campus, it's so nice, isn't it? To celebrate this meaningful day, the ACM team of HDU hold some fuuny games. Especially, there will be a game named "crashing color balloons".

There will be a n*n matrix board on the ground, and each grid will have a color balloon in it.And the color of the ballon will be in the range of [1, 50].After the referee shouts "go!",you can begin to crash the balloons.Every time you can only choose one kind of balloon to crash, we define that the two balloons with the same color belong to the same kind.What's more, each time you can only choose a single row or column of balloon, and crash the balloons that with the color you had chosen. Of course, a lot of students are waiting to play this game, so we just give every student k times to crash the balloons.

Here comes the problem: which kind of balloon is impossible to be all crashed by a student in k times.

Input

There will be multiple input cases.Each test case begins with two integers n, k. n is the number of rows and columns of the balloons (1 <= n <= 100), and k is the times that ginving to each student(0 < k <= n).Follow a matrix A of n*n, where Aij denote the color of the ballon in the i row, j column.Input ends with n = k = 0.

Output

For each test case, print in ascending order all the colors of which are impossible to be crashed by a student in k times. If there is no choice, print "-1".

Sample Input

Sample Output

Author

8600

Source

“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛

题意：在一个n*n的矩阵里有很多气球，不同的数字代表不同的气球，我们每次可以打破一行的气球或者一列的气球，现在问你，所有气球里面，不能在k次以内全部打破的气球是多少，按照数字从小到大输出

思路：枚举所有的气球，对每一种气球做一次最小顶点覆盖，x集合是行，y集合是列，因为一个点可以由这一行来打破，也可以由一列来打破

并且同一行的行坐标相等，也就是能打破一整行了，从小到大枚举即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 110
int n,k,cnt;
int num[N*N],m[N][N],ma[N][N];
int line[N],vis[N],last[N*N];
void f(int t)
{
    for(int i=0; i<cnt; i++)
        if(num[i]==t)
            return;
    num[cnt++]=t;
}
int can(int t)
{
    for(int i=1; i<=n; i++)
    {
        if(!vis[i]&&ma[t][i])
        {
            vis[i]=1;
            if(line[i]==-1||can(line[i]))
            {
                line[i]=t;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int t;
    while(~scanf("%d %d",&n,&k)&&(n+k))
    {
        cnt=0;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&m[i][j]);
                f(m[i][j]);
            }
        }
        sort(num,num+cnt);
        int s=0;
        for(int i=0; i<cnt; i++)
        {
            memset(ma,0,sizeof(ma));
            memset(line,-1,sizeof(line));
            for(int l=1; l<=n; l++)
                for(int j=1; j<=n; j++)
                    if(m[l][j]==num[i])
                        ma[l][j]=1;
            int ans=0;
            for(int i=1; i<=n; i++)
            {
                memset(vis,0,sizeof(vis));
                if(can(i)) ans++;
            }
            if(ans>k) last[s++]=num[i];
        }
        if(s==0) printf("-1\n");
        else
        {
            for(int i=0; i<s-1; i++)
                printf("%d ",last[i]);
            printf("%d\n",last[s-1]);
        }
    }
    return 0;
}