HDU 2236 无题II
思路:行列仅仅能一个,想到二分图,然后二分区间长度,枚举下限。就能求出哪些边是能用的,然后建图跑二分图,假设最大匹配等于n就是符合的
代码:
#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; }