# 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

x = sum( a ) / sum( b )
x * sum( b ) = sum( a )

x * b[ i ] = a[ i ]

a[ i ] - x * b[ i ]

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;
}
```