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

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

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

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

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

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  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<n;i++)
 31         scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].p);
 32     memset(Gram,0,sizeof(Gram));
 33     for(i=0;i<n;i++)
 34         for(j=0;j<n;j++)
 35         {
 36             Gram[i][j]=Dis(i,j);
 37         }
 38     return ;
 39 }
 40 void Build_Mst()
 41 {
 42     Mst_W=0;
 43     memset(Mst,0,sizeof(Mst));
 44     int i;
 45     for(i=0;i<n-1;i++)
 46     {
 47         Mst[i].e=i+1;
 48         Mst[i].s=0;
 49         Mst[i].w=Gram[0][i+1];
 50     }
 51     N_seq[0]=0;
 52     for(i=0;i<n-1;i++)
 53     {
 54         double min=99999999;
 55         int j,k;
 56         Edge temp;
 57         for(j=i;j<n-1;j++)if(min>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<n-1;j++)
 64         {
 65         int    q=Mst[j].e;
 66             if(Gram[k][q]<Mst[j].w)
 67             {
 68                 Mst[j].w=Gram[k][q];
 69                 Mst[j].s=k;
 70             }
 71         }
 72     }
 73 }
 74 void Solve()
 75 {
 76     ans=0;
 77     int i,j,k;
 78     for(i=0;i<n-1;i++)
 79     {
 80         int p=0;
 81         for(j=0;j<i+1;j++)
 82             for(k=i+1;k<=n-1;k++)
 83             {
 84                 if(p<node[N_seq[j]].p+node[N_seq[k]].p)
 85                     p=node[N_seq[j]].p+node[N_seq[k]].p;
 86             }
 87         if(p*1.0/(Mst_W-Mst[i].w)>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 }