题意:
从矩阵每行中找一个数( 没有2个数在同一列 ) 使得找出来的数中最大值和最小值差 最小, 输出差值
首先设矩阵中最小的数是 vmin , 最大的数是 vmax, 则答案一定 [0, vmax - vmin]
显然找出来的数一定在 区间 [ 0 + x, 0 + ans + x ] ( x为合法值)
枚举x,如果能找到匹配出的结果 都是在这个区间上,说明这个区间合法 => 这个ans合法,
二分至ans ,再判断,注意二分的上下
#include<stdio.h>
#include<string.h>
#define max Max
#define min Min
#define N 105
int map[N][N], n, vmin, vmax;
int lie[N], vis[N], p, max, min, mid;
bool match(int x){
for(int i = 1; i <= n; i++)
{
if(vis[i])continue;
if(map[x][i] > p + mid || map[x][i] < p)continue;
vis[i] = 1;
if( !lie[i] || match(lie[i])){
lie[i] = x;
return true;
}
}
return false;
}
bool solve(){
memset(lie, 0, sizeof(lie ));
for(int i = 1; i <= n; i++)
{
memset(vis, 0, sizeof(vis));
if( !match(i) )return false;
}
return true;
}
int main(){
int T, i, j; scanf("%d",&T);
while(T--){
vmin = 100;
vmax = 0;
scanf("%d",&n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
scanf("%d",&map[i][j]);
if(vmin > map[i][j]) vmin = map[i][j];
if(vmax < map[i][j]) vmax = map[i][j];
}
min = 0, max = vmax - vmin;
while( 1 )
{
bool ok = false;
mid = (min + max) >>1 ;
for(p = vmin; p + mid <= vmax ; p++)
{
if(solve()) { ok = true; break; }
}
if( ok )//如果存在一个匹配使得所有数在区间 [p, p+mid]
{
max = mid;
}
if(min == mid)break;
if(!ok ) min = mid;
}
printf("%d\n",max); //结果区间是在[0+x, 0+max +x]
}
return 0;
}
/*
99
1
1
2
1 2
3 4
3
1 2 3
4 5 6
7 8 9
3
9 7 8
6 4 2
1 5 3
ans:
0
1
4
3
*/