LA 5717枚举+最小生成树回路性质

  1 /*LA 5717
  2 《训练指南》P343
  3 最小生成树的回路性质
  4 在生成的最小生成树上，新增一条边e(u,v)
  5 若原图上u到v的路径的最大边大于e，则删除此边，加上e，否则不变。
  6 
  7 若原图上u到v的路径的最大边的产生：BFS/DFS都可 ，nm的复杂度，从每个点出发，找到每条边，更新最大即可
  8 */
  9 
 10 #include<iostream>
 11 #include<string.h>
 12 #include<stdio.h>
 13 #include<stdlib.h>
 14 #include<cmath>
 15 #include<algorithm>
 16 #include<queue>
 17 #include<stack>
 18 #include<set>
 19 #include<map>
 20 #define LL unsigned long long
 21 #define maxn 1010
 22 #define INF 99999
 23 using namespace std;
 24 
 25 double X[maxn];
 26 double Y[maxn];
 27 int Peo[maxn];
 28 int p[maxn];
 29 double L;//最小生成树总长度
 30 double MaxDis[maxn][maxn];
 31 int n,cnt;
 32 
 33 double nextnum()
 34 {
 35     double x;
 36     scanf("%lf",&x);
 37     return x;
 38 }
 39 int nextint()
 40 {
 41     int x;
 42     scanf("%d",&x);
 43     return x;
 44 }
 45 
 46 struct Edge
 47 {
 48     double u,v,dis;
 49     bool operator<(const Edge&x)const
 50     {
 51         return dis<x.dis;
 52     }
 53     void print()
 54     {
 55         cout<<"u="<<u<<","<<"v="<<v<<","<<"dis="<<dis<<endl;
 56     }
 57 } e[maxn*maxn];
 58 
 59 vector<Edge>edges;//存储新图的边
 60 vector<int>G[maxn];//记录临街的边号
 61 
 62 double Dis(int i,int j)
 63 {
 64     double x1=X[i],x2=X[j],y1=Y[i],y2=Y[j];
 65     return (sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
 66 }
 67 
 68 int findx(int x)
 69 {
 70     if (p[x]==x) return x;
 71     else return p[x]=findx(p[x]);
 72 }
 73 
 74 void merge(int x,int y)
 75 {
 76     int px=findx(x);
 77     int py=findx(y);
 78     p[px]=py;
 79 }
 80 
 81 void init()
 82 {
 83     cin>>n;
 84     cnt=0;L=0;
 85     for(int i=1; i<=n; i++)
 86     {
 87         X[i]=nextnum();//坐标值实数
 88         Y[i]=nextnum();
 89         Peo[i]=nextint();
 90     }
 91     for(int i=1; i<=n; i++)
 92         for(int j=1; j<=n; j++)
 93         {
 94             if (i==j) continue;
 95             e[cnt++]=(Edge){i,j,Dis(i,j)};//建图
 96         }
 97 }
 98 
 99 void prim()//最小生成树&&构建新的图
100 {
101     for(int i=1;i<=n;i++) G[i].clear();
102     edges.clear();
103     for(int i=1; i<=n; i++) p[i]=i;
104     sort(e,e+cnt);
105 
106     for(int i=0; i<cnt; i++)
107     {
108         int u=e[i].u,v=e[i].v;
109         double dis=e[i].dis;
110         int pu=findx(u),pv=findx(v);
111         if (pu==pv) continue;
112         L+=dis;
113         merge(u,v);
114         edges.push_back((Edge){u,v,dis});
115         G[u].push_back(edges.size()-1);
116         edges.push_back((Edge){v,u,dis});
117         G[v].push_back(edges.size()-1);
118 
119         if (edges.size()==2*(n-1)) break;
120     }
121 }
122 typedef pair<int,double> Node;//<上一个点，由起点到上一个点的通路上的最大值>
123 void max_dis()//找到最小生成树上的任意两点之间的通路的最大的边的长度，网上大多数版本是DFS实现，故写了BFS
124 {
125     memset(MaxDis,0,sizeof(MaxDis));
126     bool mark[maxn];
127     for(int i=1;i<=n;i++)
128     {
129         memset(mark,0,sizeof(mark));
130         queue<Node>Q;
131         Q.push(make_pair(i,0));
132         while(!Q.empty())
133         {
134             Node Kn=Q.front();Q.pop();
135             int u=Kn.first;double dis=Kn.second;
136             if (mark[u]) continue;
137             mark[u]=true;
138             int m=G[u].size();
139             for(int j=0;j<m;j++)
140             {
141                 Edge e=edges[G[u][j]];
142                 int v=e.v;
143                 if (MaxDis[i][v]>0) continue;//important，小技巧，因为存的是双向边，所以必须消除回退的影响
144                 dis=MaxDis[i][v]=max(Dis(u,v),dis);
145                 Q.push(make_pair(v,dis));
146             }
147         }
148     }
149 }
150 
151 int main()
152 {
153     int cas=0;
154     cin>>cas;
155     while(cas--)
156     {
157         init();
158         prim();
159         max_dis();
160         double ans=0;
161         for(int i=2; i<=n; i++)//枚举每一条道路
162             for(int j=1; j<i; j++)
163             {
164                 int A=Peo[i]+Peo[j];
165                 double B=L-MaxDis[i][j];
166                 ans=max(ans,A/B);
167             }
168         printf("%.2lf
",ans);
169     }
170     return 0;
171 }