HDU 4081 Qin Shi Huang's National Road System [次小生成树]

题意：

秦始皇要建路，一共有n个城市，建n-1条路连接。

给了n个城市的坐标和每个城市的人数。

然后建n-2条正常路和n-1条魔法路，最后求A/B的最大值。

A代表所建的魔法路的连接的城市的市民的人数的和，B 代表n-2条正常路的长度的和。

思路：

这题是次小生成树的变形，所谓次小生成树的核心应该是记录树上节点间的路中最大的边的权重，然后将这条边替换为非最小生成树中的边，然后枚举找到最小值。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#define INF 0x3f3f3f3f
using namespace std;
struct city{
    int x,y,p;
};
city jilu[1005];
int n,from[1005];
double dp[1005][1005],dis[1005],total;
bool vis[1005];
double cal(city a,city b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void prim(int pos){
    vis[pos]=1;
    for(int i=0;i<n;i++){
        if(dis[i]>cal(jilu[pos],jilu[i])){
            dis[i]=cal(jilu[pos],jilu[i]);
            from[i]=pos;
        }
    }
    int next=-1;
    double mmin=1e32;
    for(int i=0;i<n;i++){
        if(vis[i]==0&&mmin>dis[i]){
            mmin=dis[i];
            next=i;
        }
    }
    if(next>0){
        for(int i=0;i<n;i++){
            if(vis[i]){
                dp[i][next]=max(dp[i][from[next]],mmin);
            }
        }
        total+=mmin;
        prim(next);
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&jilu[i].x,&jilu[i].y,&jilu[i].p);
        }
        for(int i=0;i<n;i++){
            dis[i]=1e32;
        }
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        total=0;
        prim(0);
        double ans=-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i!=j){
                    ans=max(ans,(jilu[i].p+jilu[j].p)*1.0/(total-max(dp[i][j],dp[j][i])));
                }
            }
        }
        printf("%.2lf
",ans);
    }
}