HR Spanning Tree Fraction ( 最優比例生成樹, Binary Search, Spanning Tree )

Programming Problems and Competitions :: HackerRank

題意：
N 個點 M 個邊，第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹，使得 sum( a ) / sum( b ) 最大。

制約：
2 ≤ N ≤ 1e5
N - 1≤ M ≤ 1e5
1 ≤ a[ i ], b[ i ] ≤ 100

解法：
裸的最優比例生成樹。
聽說有這樣的東西也可以解這個，但我看不懂：
日月卦長的模板庫: [ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃
考慮對答案二分搜，假設為 x：
那麼條件可以改寫成：
x = sum( a ) / sum( b )
x * sum( b ) = sum( a )
考慮獨立：
x * b[ i ] = a[ i ]
那麼，取盡量多的 i 使得以下式子越大一定越好：
a[ i ] - x * b[ i ]
取完之後，如果發現總和為 0 以上，那這個 x 以上有解。
否則這個 x 以上無解。
看起來就很有單調性，嗯。

時間 / 空間複雜度：
O( M * lg ( M * max( a, b ) ) )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 1e5;
const int MAXM = ( int ) 1e5;

int N, M;
int U[ MAXM ], V[ MAXM ], A[ MAXM ], B[ MAXM ];

int fa[ MAXM ];
int find( int x ){
  return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] );
}
bool unite( int x, int y ){
  int a = find( x );
  int b = find( y );
  if( a == b ) return 0;
  fa[ a ] = b;
  return 1;
}

int ord[ MAXM ];
double kruskal( double t, bool print ){
  for( int i = 0; i < M; ++i ){
    ord[ i ] = i;
  }
  sort( ord, ord + M, [ & ]( int i, int j ){
                        return 1.0 * A[ i ] - t * B[ i ] > 1.0 * A[ j ] - t * B[ j ];
                      } );
  for( int i = 0; i < M; ++i ){
    fa[ i ] = i;
  }
  int p = 0, q = 0;
  double res = 0.0;
  for( int i = 0; i < M; ++i ){
    if( unite( U[ ord[ i ] ], V[ ord[ i ] ] ) ){
      p += A[ ord[ i ] ];
      q += B[ ord[ i ] ];
      res += 1.0 * A[ ord[ i ] ] - t * B[ ord[ i ] ];
    }
  }
  if( print ){
    int g = __gcd( p, q );
    cout << p / g << "/" << q / g << endl;
  }
  return res;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < M; ++i ){
    cin >> U[ i ] >> V[ i ] >> A[ i ] >> B[ i ];
  }
  double lb = 0.0, ub = 1e7;
  for( int i = 0; i < 100; ++i ){
    double mid = ( lb + ub ) / 2;
    if( kruskal( mid, 0 ) >= 0.0 ){
      lb = mid;
    } else{
      ub = mid;
    }
  }
  kruskal( lb, 1 );
  return 0;
}