题目内容
这是一个简单的游戏，在一个\(n×n\)的矩阵中，找\(n\)个数使得这\(n\)个数都在不同的行和列里并且要求这\(n\)个数中的最大值和最小值的差值最小。
输入格式
输入一个整数\(T\)，表示\(T\)组数据。
对于每组数据第一行输入一个正整数\(n(1\le n\le 100)\)表示矩阵的大小。
接着输入\(n\)行，每行\(n\)个数\(x(0\le x\le 100)\)。
输出格式
对于每组数据输出一个数表示最小差值。
样例输入
样例输出
思路
对于找出来的\(n\)个数，均属于区间\([l,r]\),那么答案就是\(r-l\)。所以枚举区间然后进行二分图匹配，让所有可能的匹配权值都属于这个区间即可。
二分图最大匹配+二分答案。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=100+10;
const int INF=0x3f3f3f3f;
int n,ans,Min,Max;
int g[maxn][maxn],match[maxn];
bool vis[maxn];
bool Find(int u){
for(int i=1;i<=n;i++){
if(!vis[i]&&g[u][i]>=Min&&g[u][i]<=Max){
vis[i]=1;
if(!match[i]||Find(match[i])){
match[i]=u;
return true;
}
}
}
return false;
}
bool judge(){
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));//这里记得初始化下
if(!Find(i))
return false;
}
return true;
}
int main(){
int T,minl,maxr;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
maxr=0;minl=INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&g[i][j]);
minl=min(g[i][j],minl);
maxr=max(g[i][j],maxr);//找到左右边界
}
}
int l=0;
int r=maxr-minl;//注意所求的答案是最小差值
ans=0;
while(l<=r){
bool flag=false;
int mid=(l+r)/2;
for(int i=minl;i+mid<=maxr;i++){
Min=i;Max=i+mid;
if(judge()){
flag=true;
break;
}
}
if(flag){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}