1 // hdu2236
2 // Graph Match binary search + enumeration + bipartite
3 // Dec.26 2014
4
5 #include <cstdio>
6 #include <cstring>
7 #include <algorithm>
8
9 #define MaxN 111
10 #define ACCEPT
11
12 int G[MaxN][MaxN], T, n, max_edge, min_edge, l, r, mid, enum_edge, gx[MaxN], gy[MaxN];
13 bool vis[MaxN], is_match;
14
15 bool dfs(int u)
16 {
17 for(int i = 1; i <= n; ++i){
18 if(G[u][i] >= enum_edge && G[u][i] <= enum_edge + mid && vis[i] == false){
19 vis[i] = true;
20 if(gy[i] == -1 || dfs(gy[i]) == true){
21 gy[i] = u;
22 gx[u] = i;
23 return true;
24 }
25 }
26 }
27 return false;
28 }
29
30 bool hungry()
31 {
32 memset(gx, -1, sizeof(gx));
33 memset(gy, -1, sizeof(gy));
34 for(int i = 1; i <= n; ++i){
35 memset(vis, false, sizeof(vis));
36 if(dfs(i) == false)
37 return false;
38 }
39 }
40
41 int main(int argc, char const *argv[])
42 {
43 #ifndef ACCEPT
44 freopen("in.txt","r",stdin);
45 #endif
46 scanf("%d", &T);
47 while(T--){
48 // input , get the max num and min num
49 max_edge = -1;
50 min_edge = 101;
51 scanf("%d", &n);
52 for(int i = 1; i <= n; ++i){
53 for(int j = 1; j <= n; ++j){
54 scanf("%d", &G[i][j]);
55 max_edge = std::max(G[i][j], max_edge);
56 min_edge = std::min(G[i][j], min_edge);
57 }
58 }
59 //
60 l = 0;
61 r = max_edge - min_edge;
62 while(true){
63 mid = (l + r) >> 1;
64 is_match = false;
65 for(enum_edge = min_edge; enum_edge + mid <= max_edge; ++enum_edge){
66 if(hungry() == true){
67 is_match = true;
68 break;
69 }
70 }
71 if(is_match == true)
72 r = mid;
73 if(l == mid)
74 break;
75 if(is_match == false)
76 l = mid;
77 }
78 printf("%d
", r);
79 }
80 return 0;
81 }
