本文主要是介绍【UVALive】5713 Qin Shi Huang's National Road System 最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【UVALive】5713 Qin Shi Huang's National Road System
题目大意：秦朝有n个城市，需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路，不花钱，也不用劳动力，但只能修一条路，因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短（这样可以节省劳动力），还希望法术连接的两个城市的人口之和A尽量大，因此下令寻找一个使得A/B最大的方案。你的任务是找到这个方案。
任意两个城市之间都可以修路，长度为两个城市之间的欧几里德距离。
题目分析：
本题是全局最小瓶颈路的应用。
因为法术只能修一条边，所以我们枚举路两端的城市u，v。A/B = (u,v)两城市人口之和/(最小生成树权值 - (u,v)唯一路径上的最长边)。
(u,v)最长边就是(u,v)的最小瓶颈路。我们可以预处理出(u,v)之间唯一路径上的最大权maxcost[u][v]。那么问题就可以解决。
怎么求maxcost[u][v]？
我们可以DFS，也可以直接在prim中求得。
只要访问一个结点v时，考虑所有已经访问的结点x，更新maxcost[v][x] = max ( maxcost[x][u] , cost[u][v])。其中u是v的父节点，cost[u][v]是树边。
下面我给出prim中求的方法。（DFS的就算了吧= =，效率没这个高）
PS：用了优先队列还跑的满，弃疗。。
代码如下：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std ;#define clear( A , X ) memset ( A , X , sizeof A )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define FF( i , a , b ) for ( int i = a ; i <= b ; ++ i )const int maxN = 1005 ;
const int oo = 0x3f3f3f3f ;
const double eps = 1e-8 ;struct City {int x , y , num ;
} ; struct MST {double d[maxN] ;double dist[maxN][maxN] ;double maxcost[maxN][maxN] ;int done[maxN] ;int fa[maxN] ;void Init () {clear ( maxcost , 0 ) ;clear ( done , 0 ) ;}double Prim ( int n ) {double ans = 0 ;REP ( i , n ) d[i] = oo ;d[0] = 0 ;fa[0] = 0 ;REP ( i , n ) {int u ;double m = oo ;REP ( j , n )if ( !done[j] && d[j] < m )m = d[u = j] ;ans += dist[fa[u]][u] ;REP ( i , n )if ( done[i] )maxcost[u][i] = maxcost[i][u] = max ( maxcost[fa[u]][i] , dist[fa[u]][u] ) ;done[u] = 1 ;REP ( v , n ) {if ( !done[v] && d[v] > dist[u][v] ) {d[v] = dist[u][v] ;fa[v] = u ;}}}return ans ;}
} ;MST P ;
City c[maxN] ;int sgn ( double x ) {return ( x > eps ) - ( x < -eps ) ;
}void work () {int n ;double cost , mmax = 0 ;P.Init () ;scanf ( "%d" , &n ) ;REP ( i , n )scanf ( "%d%d%d" , &c[i].x , &c[i].y , &c[i].num ) ;REP ( i , n - 1 )FF ( j , i + 1 , n - 1 ) {int x = c[i].x - c[j].x ;int y = c[i].y - c[j].y ;double tmp = sqrt ( (double) x * x + y * y ) ;P.dist[i][j] = P.dist[j][i] = tmp ;}cost = P.Prim ( n ) ;REP ( i , n - 1 )FF ( j , i + 1 , n - 1 ) {double tmp = cost - P.maxcost[i][j] ;int num = c[i].num + c[j].num ;if ( sgn ( num / tmp - mmax ) > 0 )mmax = num / tmp ;}printf ( "%.2f\n" , mmax ) ;
}int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- )work () ;return 0 ;
}
这篇关于【UVALive】5713 Qin Shi Huang's National Road System 最小生成树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
