Qin Shi Huang's National Road System

• 本题考查的是次小生成树的问题，这里的解决方法就是先使用Prim算法求解最小生成树。

• 在求解最小生成树的时候通过一个数组记录每一对顶点之间的路径上长度最长的一条边。这个由一个cost数组记录。

• 最后，再依次遍历每一对顶点，如果这对顶点不在最小生成树里面，则直接去掉这条边改成魔法边。否则就将这对顶点之间的那条路径上面最长的一条边去掉，用i,j这对顶点代替。

  #include
  #include
  #include
  #include
  #include
  #include
  #include
  using namespace std;
  const int maxn=1004;
  const int maxm=1000006;
  const int INF=0x3f3f3f3f;
  int n;//nodes
  int m;//edges
  struct node{
  int x;
  int y;
  int p;//人口
  };
  node cities[maxn];
  struct edge{
  int from;
  int to;
  double w;//distance
  };
  edge edges[maxm];
  double map[maxn][maxn];
  double mincost[maxn];
  bool used[maxn];
  int father[maxn];
  double cost[maxn][maxn];//表示i,j路径上最长的一条边的长度
  double cal(int i,int j){
  double x=(double)((cities[i].x-cities[j].x)(cities[i].x-cities[j].x)); double y=(double)((cities[i].y-cities[j].y)(cities[i].y-cities[j].y));
  return sqrt(x+y);
  }
  double prim(){
  memset(cost,0,sizeof(cost));
  for(int i=0;imap[v][u]){
  mincost[u]=map[v][u];
  father[u]=v;
  }
  }
  }
  return ans;
  }
  int main(){
  int t;
  cin>>t;
  while(t--){
  cin>>n;
  int x,y,p;
  for(int i=0;i>x>>y>>p;
  cities[i].x=x,cities[i].y=y,cities[i].p=p;
  }
  for(int i=0;i<n;i++){
  for(int j=0;j<i;j++){
  double dis=cal(i,j);
  map[i][j]=dis;
  map[j][i]=dis;
  edges[m].from=i;
  edges[m].to=j;
  edges[m++].w=dis;
  }
  map[i][i]=0;
  }
  double distance=prim();
  double ans=0;
  for(int i=0;i<n;i++){
  for(int j=0;j<n;j++){
  if(i==j)
  continue;
  if(i!=father[j]&&j!=father[i]){//i,j这条边不在最小生成树里面
  ans=max(ans,(cities[i].p+cities[j].p)/(distance-cost[i][j]));
  }else{//i,j这条边在最小生成树里面
  ans=max(ans,(cities[i].p+cities[j].p)/(distance-map[i][j]));
  }
  }
  }

      printf("%.2f\n",ans);//注意这里不需要加0.005,自动舍入为四舍五入
  }
  //system("pause");
  return 0;

  }