## HDU 2236 无题II（二分图匹配+二分）

2018年10月11日 ⁄ 综合 ⁄ 共 1049字 ⁄ 字号 评论关闭

# HDU 2236 无题II

```#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 105;

int t, n, x[N][N], have[N], hn;

int vis[N], left[N];
vector<int> g[N];

bool dfs(int u) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
vis[v] = 1;
if (left[v] == -1 || dfs(left[v])) {
left[v] = u;
return true;
}
}
return false;
}

int hungary() {
int ans = 0;
memset(left, -1, sizeof(left));
for (int i = 0; i < n; i++) {
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
return ans;
}

bool judge(int len) {
for (int i = 0; i < hn; i++) {
for (int j = 0; j < n; j++) g[j].clear();
int down = have[i], up = have[i] + len;
for (int u = 0; u < n; u++)
for (int v = 0; v < n; v++)
if (x[u][v] >= down && x[u][v] <= up)
g[u].push_back(v);
if (hungary() == n) return true;
}
return false;
}

int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
memset(vis, 0, sizeof(vis));
hn = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &x[i][j]);
if (vis[x[i][j]]) continue;
vis[x[i][j]] = 1;
have[hn++] = x[i][j];
}
int l = 0, r = 101;
while (l < r) {
int mid = (l + r) / 2;
if (judge(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
}
return 0;
}```