学步园

一道简单的最小点覆盖问题。。。

思想：

将每个点的x和y看作一条路径的两个端点。。

对于每个种类的气球。进行一次最大匹配搜索。。。

核心：

        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&a),map[i][j]=a,num[a]++;

用num数组标记出现的气球种类：后续遍历；

代码如下：

#include<stdio.h>
#include<string.h>
int map[102][102];
int link[102];
int vis[102];
int num[102];

int n,k;

int find(int a,int z)
{
    for(int i=0; i<n; i++)
    {
        if(!vis[i]&&map[a][i]==z)
        {
            vis[i]=1;
            if(link[i]==-1||find(link[i],z))
            {
                link[i]=a;
                return 1;
            }
        }
    }
    return 0;
}

int sum(int z)
{
    int res=0;
    memset(link,-1,sizeof(link));
    for(int i=0; i<n; i++)
    {
        memset(vis,0,sizeof(vis));
        if(find(i,z))
            res++;
    }
    return res;
}

int main()
{
    while(scanf("%d%d",&n,&k),n+k)
    {
        memset(num,0,sizeof(num));
        int a;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                scanf("%d",&a),map[i][j]=a,num[a]++;
        int flag=0;
        for(int i=1; i<=50; i++)
            if(num[i])
            {
                int t=sum(i);
                //printf("i-->%d  t-->%d\n",i,t);
                if(t>k)
                {
                    if(flag)
                        printf(" ");
                    printf("%d",i);
                    flag=1;
                }
            }
        if(!flag)
            printf("-1");
        printf("\n");
    }
    return 0;
}