#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back vector<int> tree[404]; bool T[403][403]; int odl[404]; queue<int> kolejka; int odp = 0; int odp1 = 10000000; int bfs(int v,int n) { for(int i = 1 ; i<=n ;++i) odl[i]=-1; odl[v]=0; kolejka.push(v); int u; int maxa=0; while(!kolejka.empty()) { u = kolejka.front(); kolejka.pop(); for(auto it : tree[u]) { if(odl[it]==-1) { odl[it]=odl[u]+1; maxa=max(odl[it],maxa); kolejka.push(it); } } } return maxa; } int BFS(int n) { odp = 0; for( int i = 1 ; i<=n ; ++i) { odp = max(bfs(i,n),odp); } return odp; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; int n; string x; bool a; for(int z = 1 ; z<=t ; ++z) { odp1 = 10000000; cin >> n; for(int i = 1 ; i<=n ; ++i) {cin >> x; for(int j = i+1 ;j <=n ; ++j) {a = x[j-1]-48; T[i][j]=a; if(a==1) { tree[i].pb(j); tree[j].pb(i); } } } /*for(int i = 1 ; i<=n ; ++i) {for( auto it : tree[i]) cout << it << " "; cout <<endl;}*/ //bfs(1,n); for(int i = 1 ; i <=n ; ++i) for(int j = i ; j<=n;++j) { if(T[i][j]==0) {T[i][j]=1; tree[i].pb(j); tree[j].pb(i); odp1 = min(odp1,BFS(n)); /*cout << "odp1 "<<odp1 <<"bfs " << BFS(n) << endl; cout << " # "<<endl;*/ /*for(int i = 1 ; i<=n ; ++i) {for( auto it : tree[i]) cout << it << " "; cout <<endl;}*/ tree[i].erase(tree[i].end()-1); tree[j].erase(tree[j].end()-1); T[i][j]=0;} } cout << odp1 << endl; for(int i = 1 ; i<=n ; ++i) tree[i].clear(); } return 0; }
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back vector<int> tree[404]; bool T[403][403]; int odl[404]; queue<int> kolejka; int odp = 0; int odp1 = 10000000; int bfs(int v,int n) { for(int i = 1 ; i<=n ;++i) odl[i]=-1; odl[v]=0; kolejka.push(v); int u; int maxa=0; while(!kolejka.empty()) { u = kolejka.front(); kolejka.pop(); for(auto it : tree[u]) { if(odl[it]==-1) { odl[it]=odl[u]+1; maxa=max(odl[it],maxa); kolejka.push(it); } } } return maxa; } int BFS(int n) { odp = 0; for( int i = 1 ; i<=n ; ++i) { odp = max(bfs(i,n),odp); } return odp; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; int n; string x; bool a; for(int z = 1 ; z<=t ; ++z) { odp1 = 10000000; cin >> n; for(int i = 1 ; i<=n ; ++i) {cin >> x; for(int j = i+1 ;j <=n ; ++j) {a = x[j-1]-48; T[i][j]=a; if(a==1) { tree[i].pb(j); tree[j].pb(i); } } } /*for(int i = 1 ; i<=n ; ++i) {for( auto it : tree[i]) cout << it << " "; cout <<endl;}*/ //bfs(1,n); for(int i = 1 ; i <=n ; ++i) for(int j = i ; j<=n;++j) { if(T[i][j]==0) {T[i][j]=1; tree[i].pb(j); tree[j].pb(i); odp1 = min(odp1,BFS(n)); /*cout << "odp1 "<<odp1 <<"bfs " << BFS(n) << endl; cout << " # "<<endl;*/ /*for(int i = 1 ; i<=n ; ++i) {for( auto it : tree[i]) cout << it << " "; cout <<endl;}*/ tree[i].erase(tree[i].end()-1); tree[j].erase(tree[j].end()-1); T[i][j]=0;} } cout << odp1 << endl; for(int i = 1 ; i<=n ; ++i) tree[i].clear(); } return 0; } |