hdu4081Qin Shi Huang's National Road System 次小生成树
分类：最小生成树dp
dp最小生成树
//给出每点的坐标和其到人口量，找一个生成树，其中有一条边造价为0//问A/B的最大值，A这条边连接的两个点的人口之和//B除了这条边以外的其他边的长度之和//先找到最小生成树，，然后枚举所有边,如果这条边是最小生成树上的边，//直接计算A/(sum-edge) ,如果不是，那么这条边加在最小生成树上会出现一个//环，去除这个环中的最长的边依然是一棵树，//用dp[u][v] 表示在最小生成树中从u到v的唯一路径所经过的最长边的大小//dp[u][v[i]] = dp[v[i]][u]= max(map[F[u]][u] , dp[F[u]][v[i]]) ;using namespace std ;const int maxn = 1010 ;const int inf = 0x3f3f3f3f ;double dp[maxn][maxn] ;double map[maxn][maxn] ;double x[maxn] , y[maxn] , p[maxn] ;int F[maxn] ;int vis[maxn] ;int v[maxn] ;double dis[maxn] ;int n ;double prim(){}int main(){}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇hdu3461Code Lock 快速幂+并查集
顶0踩0
爱的力量大到可以使人忘记一切，却又小到连一粒嫉妒的沙石也不能容纳
