hdu 1498 50 years, 50 colors（二分匹配，最小点覆盖）

题意：n*n的矩阵放置不同的颜色（不同的数字代表不同的颜色），你有k次选择，每一次只能选择某一行或某一列，可以消除该行（列）的所有颜色，问有哪几种颜色，无论怎样经过k次选择后依然无法完全抹去。

分析：依旧是将横坐标作为x集，纵坐标作为y集合进行匹配。对于某种颜色的匹配，如果他的最大匹配大于k，则该颜色在k次里无论如何都无法抹去的。

         还有一个问题就是为什么这道题是最小点覆盖，通过自己画图就知道了

        假设x｛1｝和｛1，2，3，4｝分别连接，x｛2｝和y｛3｝连接，则只用选择1，2行，就可以将所有的颜色抹去了

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=150;
int map[MAXN][MAXN];
int pre[MAXN];
int vis[MAXN];
int used[MAXN];
int ans[MAXN];
int n,k;

bool cmp(int a,int b)
{
    return a<b;
}

int find(int cur,int color)
{
    int i;
    for(i=1; i<=n; i++)
    {
        if(map[cur][i]==color && !vis[i])//对应的某一列是否存在该color
        {
            vis[i]=1;
            if(pre[i]==-1 || find(pre[i],color))//这里find的是pre【i】，刚开始这里敲错了wa了两次
            {
                pre[i]=cur;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,t,w,sum;
    int len;
    while(scanf("%d%d",&n,&k))
    {
        if(n==0 && k==0) break;
        memset(map,0,sizeof(map));
        memset(used,0,sizeof(used));

        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf("%d",&w);
                map[i][j]=w;
            }
        }
        len=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                memset(pre,-1,sizeof(pre));
                sum=0;
                if(used[map[i][j]]==0)//该颜色没有出现过
                {
                    used[map[i][j]]=1;
                    for(t=1; t<=n; t++)//枚举每一行
                    {
                        memset(vis,0,sizeof(vis));
                        sum+=find(t,map[i][j]);
                    }
                }
                if(sum>k) ans[len++]=map[i][j];
            }
        }
        if(len==0) printf("-1\n");
        else
        {
            sort(ans,ans+len,cmp);
            for(i=0;i<len;i++)
            {
                if(i) printf(" ");
                printf("%d",ans[i]);
            }
            printf("\n");
        }
    }
}

 set容器

#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#include<iostream>
using namespace std;

const int MAXN=150;

set<int>s;
int map[MAXN][MAXN];
int pre[MAXN];
int vis[MAXN];
int used[MAXN];
int ans[MAXN];
int n,k;

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

int main()
{
    int i,j,t,w,sum;
    int len;
    while(scanf("%d%d",&n,&k))
    {
        s.clear();
        if(n==0 && k==0) break;
        memset(map,0,sizeof(map));

        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                scanf("%d",&w);
                s.insert(w);
                map[i][j]=w;
            }
        }
        len=0;
        sum=0;
        set<int>::iterator iter;
        for(iter=s.begin(); iter!=s.end(); iter++)
        {
            //cout<<"值"<<*iter<<endl;
            memset(pre,-1,sizeof(pre));
            sum=0;//这里忘记了
            for(t=1; t<=n; t++)
            {
                memset(vis,0,sizeof(vis));
                sum+=find(t,*iter);
            }
            if(sum>k) ans[len++]=*iter;
        }
        if(len==0) printf("-1\n");
        else
        {
            for(i=0; i<len; i++)
            {
                if(i) printf(" ");
                printf("%d",ans[i]);
            }
            printf("\n");
        }
    }
}