hdu2336 (匈牙利最大匹配+二分)

• 2020 年 5 月 13 日
• 筆記
• 二分圖

Describe

這是一個簡單的遊戲，在一個n*n的矩陣中，找n個數使得這n個數都在不同的行和列里並且要求這n個數中的最大值和最小值的差值最小。

Input

輸入一個整數T表示T組數據。
對於每組數據第一行輸入一個正整數n(1<=n<=100)表示矩陣的大小。
接着輸入n行，每行n個數x(0<=x<=100)。

Output

對於每組數據輸出一個數表示最小差值。

Sample Input

1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

Sample Output

3

Solution

首先因為每列每行只能選一個數,自然想到二分圖匹配,讓行作為左部,列作為右部,讓列與行去匹配,當形成完備匹配(左右部點數相等,左部每個點都有對應的匹配點)時,則可取.

題目中要問最小的極值差,且n範圍很小[1,100],所以我們枚舉區間len,看看權值在某一區間[ l , l+len ]中的邊能否使圖形成完備匹配.左端點枚舉.對於區間我們用二分.

Code

#include <cmath>
#include <cstdio>
#include <cstring> 
#include <algorithm>
using namespace std;
const int maxn=100+5,Inf=0x3f3f3f3f;
int n,mat[maxn],rel[maxn][maxn],Max,Min;
bool vis[maxn];
bool Find(int u,int l,int r){
	for(int i=1;i<=n;++i){
		if(rel[u][i]<l||rel[u][i]>r)continue;
		if(!vis[i]){
			vis[i]=1;
			if(!mat[i]||Find(mat[i],l,r)){
				mat[i]=u;return 1;
			}
		}
	}
	return 0;
}
bool cd(int l,int r){
	memset(mat,0,sizeof mat);
	int cnt=0;
	for(int i=1;i<=n;++i){
		memset(vis,0,sizeof vis);
		if(Find(i,l,r))cnt++;
	}
	if(cnt==n)return 1;
	else return 0;
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		Max=0,Min=Inf;
		scanf("%d",&n);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				scanf("%d",&rel[i][j]);
				Max=max(Max,rel[i][j]);
				Min=min(Min,rel[i][j]);
			}
		}
		int l=0,r=Max-Min,ans=r;//l是區間最小值,r是區間最大值
		while(l<=r){
			int mid=((l+r)>>1);//這個外面應該加一層括號,mid是區間長度
			bool fg=0;
			for(int i=Min;i+mid<=Max;++i){//枚舉左端點
				if(cd(i,i+mid)){
					ans=min(ans,mid);
					fg=1;
					break;
				}
			}
			if(fg)r=mid-1;
			else l=mid+1;
		}
		printf("%d\n",ans);
	}
	return 0;
}