fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define mxs 1010
  5. #define inf 9999999999999.00
  6. double loc [ 2 ] [ mxs ] , cost [ mxs ];
  7. double value [ 25 ] [ mxs ];
  8. int population [ mxs ] , parent [ mxs ] , sparse [ mxs ] [ 22 ] , level [ mxs ];
  9. vector < pair < int , double > > graph [ mxs ];
  10. int p , q , a , b , n , t , m , c , k , log_;
  11. bool visited [ mxs ];
  12. priority_queue < pair < double , int > > pq;
  13. double x , y , z , w , ans , sum;
  14. void make_graph();
  15. void mst();
  16. void clear_();
  17. void dfs( int source );
  18. void make_sparse();
  19. void solution_finder();
  20. double lca();
  21. int main()
  22. {
  23.     //ios_base::sync_with_stdio(false);
  24.     //cin.tie(NULL);
  25.     scanf("%d",&t);
  26.     while ( t-- )
  27.     {
  28.         clear_();
  29.         scanf("%d",&n);
  30.         for ( int i = 1; i <= n; i++ )scanf("%lf%lf %d",&loc [ 0 ] [ i ] , &loc [ 1 ] [ i ], &population [ i ] );
  31.         make_graph();
  32.         mst();
  33.         level [ 1 ] = 0;
  34.         parent [ 1 ] = -1;
  35.         cost [ 1 ] = 0.00;
  36.         dfs( 1 );
  37.         make_sparse();
  38.         solution_finder();
  39.         printf("%.2f\n",ans);
  40.     }
  41.     return 0;
  42. }
  43. void clear_()
  44. {
  45.     //memset( value , 0.00, sizeof value );
  46.     memset( sparse , -1, sizeof sparse );
  47.     for ( int i = 0; i <= 1002; i++ )
  48.     {
  49.         visited [ i ] = 0;
  50.         graph [ i ].clear();
  51.         cost [ i ] = inf;
  52.     }
  53. }
  54. void make_graph()
  55. {
  56.     for ( int i = 1; i <= n; i++ )
  57.     {
  58.         for ( int j = 1; j <= n; j++ )
  59.         {
  60.             if ( i == j )continue;
  61.             x = loc [ 0 ] [ i ] - loc [ 0 ] [ j ];
  62.             x *= x;
  63.             y = loc [ 1 ] [ j ] - loc [ 1 ] [ i ];
  64.             y *= y;
  65.             x += y;
  66.             x = (double)sqrt( x );
  67.             graph [ i ].push_back ( { j , x } );
  68.             graph [ j ].push_back ( { i , x } );
  69.         }
  70.     }
  71. }
  72. void mst()
  73. {
  74.     parent [ 1 ] = -1;
  75.     pq.push( { 0.00 , 1 } );
  76.     cost [ 1 ] = 0.00;
  77.     while ( !pq.empty() )
  78.     {
  79.         a = pq.top().second;
  80.         pq.pop();
  81.         if ( visited [ a ] )continue;
  82.         visited [ a ] = 1;
  83.         int sz = graph [ a ].size();
  84.         for ( int i = 0; i != sz; i++ )
  85.         {
  86.             b = graph [ a ] [ i ].first;
  87.             x = graph [ a ] [ i ].second;
  88.             if ( !visited [ b ] && cost [ b ] > x )
  89.             {
  90.                 pq.push( { x , b } );
  91.                 cost [ b ] = x;
  92.                 parent [ b ] = a;
  93.             }
  94.         }
  95.     }
  96.     for ( int i = 0; i <= n; i++ )
  97.     {
  98.         graph [ i ].clear();
  99.         visited [ i ] = 0;
  100.     }
  101.     sum = 0.00;
  102.     for ( int i = 2; i <= n; i++ )
  103.     {
  104.         a = parent [ i ];
  105.         sum += cost [ i ];
  106.         graph [ a ].push_back ( { i , cost [ i ] } );
  107.         graph [ i ].push_back ( { a , cost [ i ] } );
  108.         parent [ i ] = -1;
  109.     }
  110. }
  111. void dfs( int source )
  112. {
  113.     visited [ source ] = 1;
  114.     int sz = graph [ source ].size();
  115.     for ( int i = 0; i != sz; i++ )
  116.     {
  117.         int lol = graph [ source ] [ i ].first;
  118.         if ( !visited [ lol ] )
  119.         {
  120.             parent [ lol ] = source;
  121.             level [ lol ] = level [ source ] + 1;
  122.             cost [ lol ] = graph [ source ] [ i ].second;
  123.             dfs( lol );
  124.         }
  125.     }
  126. }
  127. void make_sparse()
  128. {
  129.     value [ 0 ] [ 1 ] = 0.00;
  130.     for ( int i = 2; i <= n; i++ )sparse [ 0 ] [ i ] = parent [ i ],value [ 0 ] [ i ] = cost [ i ];
  131.     for ( int j = 1; ( 1<<j ) <= n ; j++ )
  132.         for ( int i = 2 ; i <= n; i++ )
  133.             if ( sparse [ j - 1 ] [ i ] != -1 )
  134.             {
  135.                 sparse [ j ] [ i ] = sparse [ j - 1 ] [ sparse [ j - 1 ] [ i ] ];
  136.                 value [ j ] [ i ] = max ( value [ j - 1 ] [ i ] , value [ j - 1 ] [ sparse [ j - 1 ] [ i ] ] );
  137.             }
  138. }
  139. void solution_finder()
  140. {
  141.     ans = 0.00;
  142.     for ( int i = 1; i <= n; i++ )
  143.         for ( int j = 1; j <= n; j++ )
  144.         {
  145.             if ( i == j )continue;
  146.             p = i , q = j;
  147.             w = lca();
  148.             x = ( double )( population [ i ] + population [ j ] );
  149.             ans = max ( ans , ( double )( x / ( sum - w ) ) );
  150.         }
  151. }
  152. double lca()
  153. {
  154.     if ( level [ p ] < level [ q ] )swap( p , q );
  155.     log_ = 1;
  156.     while ( level [ p ] >= ( 1<< ( log_ + 1 ) ) )log_++;
  157.     w = 0.00;
  158.  
  159.     for ( int i = log_; i >= 0; i-- )
  160.         if ( sparse [ i ] [ p ] != -1 && ( level [ p ] - ( 1<<i ) ) >= level [ q ] )
  161.         {
  162.             w = max ( w , value [ i ] [ p ] );
  163.             p = sparse [ i ] [ p ];
  164.         }
  165.  
  166.  
  167.     if ( p == q )return w;
  168.  
  169.     for ( int i = log_; i >= 0; i-- )
  170.     {
  171.         if ( sparse [ i ] [ p ] != -1 && sparse [ i ] [ p ] != sparse [ i ] [ q ] )
  172.         {
  173.             w = max ( w , value [ i ] [ p ] );
  174.             w = max ( w , value [ i ] [ q ] );
  175.             p = sparse [ i ] [ p ];
  176.             q = sparse [ i ] [ q ];
  177.         }
  178.     }
  179.  
  180.     w = max ( w , value [ 0 ] [ p ] );
  181.     w = max ( w , value [ 0 ] [ q ] );
  182.     return w;
  183. }
  184.  
Success #stdin #stdout 0s 4172KB
comments (?)
stdin
copy 
2
4
1 1 20
1 2 30
200 2 80
200 1 100
3
1 1 20
1 2 30
2 2 40
stdout
copy 
65.00
70.00
https://ideone.com/IyfujT
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!