hdu1498最小點覆蓋

hdu1498最小點覆蓋

1.題意：(很是重要，理解了題意才能有轉換為最小點覆蓋的思路)，對於一個n*n的矩陣，裡面有一些顏色不同的氣球(用1~50標記種類)，給你K次機會，每次機會可以把某一行或者某一列中的某一種顏色全部消滅，問你K次消滅之後，有哪些顏色是你不能消滅完的....拿題目的案例 2 來畫圖：

我們這裡只有K=1次機會去消除,,我們只有四種方式，從圖中來看，1次機會我們不可能把1號顏色全部消除，但是有能把2號顏色消除的情況

2.分析：那麼對於題目，我們的解決方案就是要把圖中所有的顏色枚舉一次，比如枚舉 i 號顏色，那麼就先求出全部消除 i 號顏色要用到的最小次數，那麼對於求解這次最小次數...我們就考慮用到二分匹配匈牙利算法，並且是一個“最小點覆蓋”的思路

#include
#include
#include
using namespace std;

#define MAX 101

int n,k;
int map[MAX][MAX];//存放整個圖 map[i][j]的值 就是該方格的顏色
int link[MAX];
bool color[MAX],vis[MAX];//color[i] 為真 表示i號顏色在整個map中出現

bool dfs(int i,int co)//本次dfs過程中 是用 第i行 顏色為 co 去匹配，
{
	for(int j = 0; j < n; j ++)
	{
		if(!vis[j] && map[i][j] == co)
		{
			vis[j] = true;
			if(link[j] == -1 || dfs(link[j],co))
			{
				link[j] = i;return true;
			}
		}
	}
	return false;
}

int KM(int co)
{
	memset(link,-1,sizeof(link));
	int ans=0;
	for(int i = 0; i < n ; i ++)
	{
		memset(vis,false,sizeof(vis));
		if(dfs(i,co)) ans++;
	}
	return ans;
}

int main()
{
	int i,j;
	int ans[51],tol;//ans[] 存放的是要輸出的不能消滅的顏色號，tol表示不能消滅的顏色數量
	while(scanf("%d%d",&n,&k),n+k)
	{
		memset(color,false,sizeof(color));
		memset(map,0,sizeof(map));
		for(i = 0; i < n; i ++)
		{
			for(j = 0; j < n; j ++)
			{
				scanf("%d",&map[i][j]);
				color[map[i][j]] = true;
			}
		}
		tol=0;
		for(i = 1; i <= 50; i ++)
		{
			if(color[i])//注意這裡表示 i 號顏色是不是有的
			{
				if(KM(i) > k)//如果匹配最小消除i號顏色用到的次數大於k 意思就是不能消滅
					ans[tol++]=i;
			}
		}
		sort(ans,ans+tol);//注意排序
		if(tol == 0)
			printf("-1");
		else
			for(i = 0; i < tol; i ++)
				i == 0 ? printf("%d",ans[i]):printf(" %d",ans[i]);//這裡是簡單的格式控制，兩數據中有空格
		printf("\n");
	}
	return 0;
}