hdu1498 50 years, 50 colors --- 最小点覆盖

给一个矩阵，里面有一些不同颜色的气球。每次能够消灭一行或一列中某一种颜色的气球，问你在k次及以内，有哪些颜色的气球是不管怎样也消不完的。

那么思路就是，对每一种颜色的气球求最小点覆盖。>k 则为答案。

相当于 poj3041的加强版，由于矩阵中不是每个点都是等价的。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

const int maxn=105;

using namespace std;

int mx[maxn],my[maxn],vis[maxn],e[maxn][maxn],n,cnt,mp[maxn][maxn],mat[maxn],ans[maxn];

map<int,int> mmp;

int path(int i)

{

    int j;

    for(j=0;j<n;j++)

    {

        if(e[i][j]&&!vis[j])

        {

            vis[j]=1;

            if(my[j]==-1||path(my[j]))

            {

                mx[i]=j;

                my[j]=i;

                return 1;

            }

        }

    }

    return 0;

}

int hungry()

{

    int res=0;

    memset(mx,-1,sizeof mx);

    memset(my,-1,sizeof my);

    for(int i=0;i<n;i++)

    {

        if(mx[i]==-1)

        {

            memset(vis,0,sizeof vis);

            res+=path(i);

        }

    }

    return res;

}

int main()

{

    int k,i,j,m,p,x;

    while(scanf("%d%d",&n,&k)&&(n||k))

    {

        cnt=1;

        mmp.clear();

        for(i=0;i<n;i++)

            for(j=0;j<n;j++)

            {

                scanf("%d",&mp[i][j]);

                if(mmp[mp[i][j]]) continue;

                else

                {

                    mmp[mp[i][j]]=cnt;

                    mat[cnt++]=mp[i][j];

                }

            }

        m=0;

        for(p=1;p<cnt;p++)

        {

            x=mat[p];

            memset(e,0,sizeof e);

            for(i=0;i<n;i++)

                for(j=0;j<n;j++)

                    if(mp[i][j]==x) e[i][j]=1;

            if(hungry()>k) ans[m++]=x;

        }

        if(m==0) printf("-1\n");

        else

        {

            sort(ans,ans+m);//wa了一次。

。

            printf("%d",ans[0]);

            for(i=1;i<m;i++)

                printf(" %d",ans[i]);

            puts("");

        }

    }

    return 0;

}