LETTers比赛第七场 Qin Shi Huang's National Road System-白红宇

LETTers比赛第七场 Qin Shi Huang's National Road System

阅读量：4673 次

发布时间：2019-06-09

本文共 1411 字，大约阅读时间需要 4 分钟。

这道题和上次周杰出的相似三角形题，是我们校队在2011区预赛中做对的唯一的两道题，最终校队是以罚时的微弱劣势丧失银牌~

解题思路很多种，这里提供一种自己的思路

首先题目求解最小生成树（MST）；这里用Prim算法并把最小生成树边的集合存起来；

然后依次去掉每条边，考虑这个n-2边的图，两个for循环依次枚举这两个连通图上的点；得出最优值。

View Code

1 #include
      
         2 #include
       
          3 #include
        
           4 const int maxn=1000+10;  5 typedef struct  6 {  7     int x,y;  8     int p;  9 }Node; 10 typedef struct 11 { 12     int s,e; 13     double w; 14 }Edge; 15 Node node[maxn]; 16 Edge Mst[maxn]; 17 double Gram[maxn][maxn]; 18 double Mst_W; 19 double ans; 20 int N_seq[maxn]; 21 int n;//节点数 22 double Dis(int s,int e) 23 { 24     return (double)sqrt((node[s].x-node[e].x)*(node[s].x-node[e].x)+(node[s].y-node[e].y)*(node[s].y-node[e].y)); 25 } 26 void Build_Gram() 27 { 28     scanf("%d",&n); 29     int i,j; 30     for(i=0;i
         
          Mst[j].w) 58         {min=Mst[j].w;k=j;} 59         Mst_W+=min; 60         N_seq[i+1]=Mst[k].e; 61         temp=Mst[i];Mst[i]=Mst[k];Mst[k]=temp; 62         k=Mst[i].e; 63         for(j=i+1;j
          
           ans) 88             ans=p*1.0/(Mst_W-Mst[i].w); 89     } 90 } 91 int main() 92 { 93     int tt; 94     scanf("%d",&tt); 95     while(tt--) 96     { 97         Build_Gram(); 98         Build_Mst(); 99         Solve();100         printf("%.2lf\n",ans);101     }102     return 0;103 }