#include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define iii tuple<int,int,int> #define fi first #define se second #define endl '\n' #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n; string s[405]; int apsp[405][405]; bitset<405> has[405][405]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); int TC; cin>>TC; while (TC--){ cin>>n; rep(x,0,n) cin>>s[x]; rep(x,0,n) rep(y,0,n) apsp[x][y]=1e9; rep(x,0,n) apsp[x][x]=1; rep(x,0,n) rep(y,0,n) if (s[x][y]=='1') apsp[x][y]=1; rep(k,0,n) rep(i,0,n) rep(j,0,n) apsp[i][j]=min(apsp[i][j],apsp[i][k]+apsp[k][j]); rep(x,0,n) rep(y,0,n) has[x][y].reset(); rep(x,0,n) rep(y,0,n) has[x][apsp[x][y]][y]=1; rep(x,0,n) rep(y,1,n) has[x][y]|=has[x][y-1]; bitset<405> one; rep(x,0,n) one[x]=1; int ans=n-2; rep(a,0,n) rep(b,a+1,n){ while (ans){ bool ok=true; rep(x,0,n){ bitset<405> bm=has[x][ans]; if (apsp[x][a]<=ans) bm|=has[b][ans-apsp[x][a]]; if (apsp[x][b]<=ans) bm|=has[a][ans-apsp[x][b]]; if (bm!=one){ ok=false; break; } } if (ok) ans--; else break; } } cout<<ans+1<<endl; } }
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 | #include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define iii tuple<int,int,int> #define fi first #define se second #define endl '\n' #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n; string s[405]; int apsp[405][405]; bitset<405> has[405][405]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); int TC; cin>>TC; while (TC--){ cin>>n; rep(x,0,n) cin>>s[x]; rep(x,0,n) rep(y,0,n) apsp[x][y]=1e9; rep(x,0,n) apsp[x][x]=1; rep(x,0,n) rep(y,0,n) if (s[x][y]=='1') apsp[x][y]=1; rep(k,0,n) rep(i,0,n) rep(j,0,n) apsp[i][j]=min(apsp[i][j],apsp[i][k]+apsp[k][j]); rep(x,0,n) rep(y,0,n) has[x][y].reset(); rep(x,0,n) rep(y,0,n) has[x][apsp[x][y]][y]=1; rep(x,0,n) rep(y,1,n) has[x][y]|=has[x][y-1]; bitset<405> one; rep(x,0,n) one[x]=1; int ans=n-2; rep(a,0,n) rep(b,a+1,n){ while (ans){ bool ok=true; rep(x,0,n){ bitset<405> bm=has[x][ans]; if (apsp[x][a]<=ans) bm|=has[b][ans-apsp[x][a]]; if (apsp[x][b]<=ans) bm|=has[a][ans-apsp[x][b]]; if (bm!=one){ ok=false; break; } } if (ok) ans--; else break; } } cout<<ans+1<<endl; } } |