1498.txt

杭电acm解题报告2001---2099.

//二分匹配,构造二分图,最小顶点覆盖(最小击打气球数)
//一边表示x,一边表示y,relation[x][邻接数]=y;
#include <cstdio>
#include <vector>
using namespace std;
#define SUCCESS 1
#define FAIL -1

int mark[110],path[51];
bool flag[110];
char map[110][110];
int n,k;
vector<vector<int> > relation;

int allocatefor(int pos)
{
    int newpos,i;
    if(flag[pos]==0) return FAIL;
    for(i=0;i<relation[pos].size();i++)
        if(mark[relation[pos][i]]==-1)
        {
            mark[relation[pos][i]]=pos;
            return SUCCESS;
        }
    for(i=0;i<relation[pos].size();i++)
    {
        newpos=mark[relation[pos][i]];
        if(newpos==-2) continue;
        mark[relation[pos][i]]=-2;
        if(allocatefor(newpos)==SUCCESS)
        {
            mark[relation[pos][i]]=pos;
            return SUCCESS;
        }
        mark[relation[pos][i]]=newpos;
    }
    flag[pos]=0;
    return FAIL;
}
void Con_BiGraph(int row , int col)
{
    int i , j , x=map[row][col];    
    for(j=col; j<n; j++)
        if(map[row][j]==x) 
        {
            relation[row].push_back(j);
            map[row][j]=-1;
        }
    for(i=row+1; i<n; i++)
        for(j=0; j<n; j++)
            if(map[i][j]==x) 
            {
                relation[i].push_back(j);
                map[i][j]=-1;
            }
}
int main()
{
    int i,j,l,x;
    bool no;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==0 && k==0)
            break;
        memset(path,0,sizeof(path));
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%d",&map[i][j]);
            
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                if(map[i][j]!=-1)
                {
                    x=map[i][j];
                    relation.clear();
                    relation.resize(n);
                    memset(mark,-1,sizeof(mark));
                    Con_BiGraph(i,j);
                    for(l=0; l<n; l++)
                    {
                        memset(flag,1,sizeof(flag));
                        if(allocatefor(l)==SUCCESS)
                            path[ x ]++;
                    }
                }
        no=true;
        for(i=1;i<=50;i++)
            if( path[i] >k)
                printf(no ? "%d" : " %d" ,i ) , no=false;
        printf(no ? "-1\n":"\n");
    }
}