hdu 1498 헝가리 알고리즘 / 최소 덮어 쓰기

http://acm.hdu.edu.cn/showproblem.php?pid=1498
처음 엔 제목 이 이해 가 안 돼 ~
가로 좌 표를 x 집합 합 종 좌표 로 y 집합 각 색상 의 좌 표를 한 변 에 대응 하고 가장 작은 점 (가로 또는 세로, 즉 사격 이 필요 한 횟수) 으로 대응 변 의 개 수 를 덮어 씁 니 다.
코드:
/*************************************************************************
	> File Name: main.cpp
	> Author: huangshuai
	> Mail: [email protected] 
	> Created Time: Sat 09 Mar 2013 02:00:24 PM CST
 ************************************************************************/

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int map[55][105][105];
int vis[105];
int link1[105];
int n;
int dfs(int i,int j)
{
	int l;
	for(l=1;l<=n;l++)
	{
		if(!vis[l]&&map[i][j][l])
		{
			vis[l]=1;
			if(link1[l]==-1||dfs(i,link1[l]))
			{
				link1[l]=j;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int k;
	int i,j;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		if(n==0&&k==0)
			break;
		memset(map,0,sizeof(map));
		int temp[55],o=0;
		memset(temp,0,sizeof(temp));
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				int t;
				scanf("%d",&t);
				map[t][i][j]=1;
				temp[t]=1;
			}
		}
		queue<int> q;
		for(i=0;i<52;i++)
		{
			if(!temp[i])
				continue;
			memset(link1,-1,sizeof(link1));
			int s=0;
			for(j=1;j<=n;j++)
			{
				memset(vis,0,sizeof(vis));
				if(dfs(i,j))
					s++;
			}
			if(s>k)
				q.push(i);
		}
		if(q.empty())
			printf("-1
"); else { printf("%d",q.front()); q.pop(); while(!q.empty()) { printf(" %d",q.front()); q.pop(); } printf("
"); } } }

좋은 웹페이지 즐겨찾기