题目
这是一个简单的游戏，在一个n*n的矩阵中，找n个数使得这n个数都在不同的行和列里并且要求这n个数中的最大值和最小值的差值最小。
输入格式
输入一个整数\(T\)表示\(T\)组数据。
对于每组数据第一行输入一个正整数\(n(1<=n<=100)\)表示矩阵的大小。
接着输入\(n\)行，每行\(n\)个数\(x(0<=x<=100)\)。
输出格式
对于每组数据输出一个数表示最小差值。
输入样例
1
4
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
输出格式
3
题解
二分答案， 二分差值， 每次用匈牙利算法检查是否合法，合法就增加差值， 不合法就减少差值， 找到最大且合法的差值
代码
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 101;
int n, a[N][N], match[N], T;
bool vis[N];
bool dfs(int u, int l, int r) {
for (int v = 1; v <= n; v++) {
if (a[u][v] >= l && a[u][v] <= r && !vis[v]) {
vis[v] = true;
if (match[v] == -1 || dfs(match[v], l, r)) {
match[v] = u;
return true;
}
}
}
return false;
}
bool hungry(int mid, int l, int r) {
int res = 0;
memset(match, -1, sizeof(match));
for (int u = 1; u <= n; u++) {
memset(vis, 0, sizeof(vis));
if (!dfs(u, l, r)) return false;
}
return true;
}
bool check(int mid) {
for (int i = 0; i + mid <= 100; i++)
if (hungry(mid, i, i + mid))return true;
return false;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
int minv = inf, maxv = -1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &a[i][j]);
minv = min(minv, a[i][j]);
maxv = max(maxv, a[i][j]);
}
int l = 0, r = maxv - minv;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
printf("%d\n", l);
}
return 0;
}