#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; int solve() { const int inf = 1<<25; int n; cin >> n; vector<vector<int>> dist(n, vector<int>(n, inf)); for(int i = 0; i < n; i++) dist[i][i] = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { char c; cin >> c; if(c == '1') dist[i][j] = 1; } } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); vector<vector<int>> memA(n, vector<int>(n, inf)); auto check = [&](int T) -> bool { for(auto &x : memA) fill(all(x), inf); auto check_edge_farthest = [&](int x, int u, int v) -> bool { int c = min(dist[v][x], dist[u][x]); if(dist[u][x] == c) swap(u, v); //u is the further point assert(dist[u][x] >= dist[v][x]); int &A = memA[u][x]; if(A == inf) { A = 0; for(int y = 0; y < n; y++) { if(dist[x][y] > T) { A = max(A, dist[u][y]); } } } return A + c <= T; }; auto check_edge = [&](int u, int v) { for(int x = 0; x < n; x++) { if(!check_edge_farthest(x, u, v)) return false; } return true; }; for(int u = 0; u < n; u++) { for(int v = 0; v < n; v++) { if(check_edge(u, v)) return true; } } return false; }; int answer = n - 1; for(int z = 1<<20; z>>=1;) if(answer - z >= 0 && check(answer - z)) answer -= z; return answer; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while(T--) { cout << solve() << '\n'; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; int solve() { const int inf = 1<<25; int n; cin >> n; vector<vector<int>> dist(n, vector<int>(n, inf)); for(int i = 0; i < n; i++) dist[i][i] = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { char c; cin >> c; if(c == '1') dist[i][j] = 1; } } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); vector<vector<int>> memA(n, vector<int>(n, inf)); auto check = [&](int T) -> bool { for(auto &x : memA) fill(all(x), inf); auto check_edge_farthest = [&](int x, int u, int v) -> bool { int c = min(dist[v][x], dist[u][x]); if(dist[u][x] == c) swap(u, v); //u is the further point assert(dist[u][x] >= dist[v][x]); int &A = memA[u][x]; if(A == inf) { A = 0; for(int y = 0; y < n; y++) { if(dist[x][y] > T) { A = max(A, dist[u][y]); } } } return A + c <= T; }; auto check_edge = [&](int u, int v) { for(int x = 0; x < n; x++) { if(!check_edge_farthest(x, u, v)) return false; } return true; }; for(int u = 0; u < n; u++) { for(int v = 0; v < n; v++) { if(check_edge(u, v)) return true; } } return false; }; int answer = n - 1; for(int z = 1<<20; z>>=1;) if(answer - z >= 0 && check(answer - z)) answer -= z; return answer; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while(T--) { cout << solve() << '\n'; } } |