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 11110 #define ACCEPT11 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 ACCEPT44         freopen("in.txt","r",stdin);45     #endif46     scanf("%d", &T);47     while(T--){48         // input , get the max num and min num49         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\n", r);79     }80     return 0;81 }