CFR 120 F. Spiders ( Tree Diameter )
題意:
給若干顆樹,現在連最少的邊使之連通,求連通後最大直徑。
數據範圍:
樹數量 1 ≤ N ≤ 100
樹大小 2 ≤ s[ i ] ≤ 100
解法:
求直徑總和即可。直徑的找法是,先對一任意一個點,找到其最遠點。該點至它的最遠點的距離即是直徑。
時間 / 空間複雜度:
O( N * S ) / O( N )
int get_dmt( const vvi &G, int u ){ int t; queue< int > que; vi vis1( G.size() ); que.emplace( u ); vis1[ u ] = 1; while( not que.empty() ){ int x = que.front(); que.pop(); t = x; for( int y : G[ x ] ) if( not vis1[ y ] ) vis1[ y ] = 1, que.emplace( y ); } int res = 0; queue< pii > q; vi vis2( G.size() ); q.emplace( 0, t ); vis2[ t ] = 1; while( not q.empty() ){ int d, x; tie( d, x ) = q.front(); q.pop(); res = d; for( int y : G[ x ] ) if( not vis2[ y ] ) vis2[ y ] = 1, q.emplace( d + 1, y ); } return res; } void solve(){ freopen( "input.txt", "r", stdin ); freopen( "output.txt", "w", stdout ); int N; cin >> N; int ans = 0; for( int i = 0; i < N; ++i ){ int s; cin >> s; vvi G( s ); for( int i = 0; i < s - 1; ++i ){ int u, v; cin >> u >> v; --u, --v; G[ u ].emplace_back( v ); G[ v ].emplace_back( u ); } ans += get_dmt( G, 0 ); } cout << ans << endl; }