HDU 1498 50 years, 50 colors (2 점 최대 일치 하 는 최소 덮어 쓰기)

제목: HDU 1498
어 지 러 워...세 사람 이 동시에 풀 었 던 이 문 제 는 결국 모두 뜻 을 잘못 이해 했다.그리고 사람마다 잘못 이해 하 는 부분 이 다르다.하지만 사례 는 다 지나 갈 수 있어...멋 있어...
제목: n * n 의 행렬 은 서로 다른 색 (서로 다른 숫자 는 서로 다른 색 을 대표 합 니 다) 을 배치 합 니 다. k 번 선택 이 있 습 니 다. 매번 한 줄 또는 한 열 만 선택 할 수 있 습 니 다. 이 줄 (열) 의 모든 색 을 없 앨 수 있 습 니 다. 몇 가지 색 이 있 는 지 물 어보 면 아무리 k 번 선택 을 한 후에 도 완전히 지 울 수 없습니다.
이 문제 의 사고방식 은 각 색깔 의 최소 조작 횟수 를 각각 구 하 는 것 이다.그리고 k 번 이상 이면 요구 에 부합 되 지 않 는 다.그리고 출력 하면 됩 니 다.

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

using namespace std;
int link[200], vis[200], cnt, head[200], n, m, mp[200][200];
struct node
{
    int u, v, next;
}edge[100000];
void add(int u, int v)
{
    edge[cnt].v=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int dfs(int u)
{
    int i;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!vis[v])
        {
            vis[v]=1;
            if(link[v]==-1||dfs(link[v]))
            {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int hungary()
{
    int i, ans=0;
    memset(link,-1,sizeof(link));
    for(i=0;i<n;i++)
    {
        memset(vis,0,sizeof(vis));
        ans+=dfs(i);
    }
    //printf("%d
",ans);
    return ans;
}
int main()
{
    int k, i, j, h, s, _hash[200], Q[200];
    while(scanf("%d%d",&n,&k)!=EOF&&n&&k)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&mp[i][j]);
            }
        }
        int tot=0;
        for(h=1;h<=50;h++)
        {
            memset(head,-1,sizeof(head));
            cnt=0;
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    if(mp[i][j]==h)
                    {
                        add(i,j);
                    }
                }
            }
            int ans=hungary();
            if(ans>k)
            {
                Q[tot++]=h;
            }
        }
        if(tot==0)
            printf("-1
");
        else
        {
            for(i=0;i<tot-1;i++)
            {
                printf("%d ",Q[i]);
            }
            printf("%d
",Q[tot-1]);
        }
    }
    return 0;
}