原题链接

考察:次小生成树

思路:

        求免去费用道路两端玩具之和A/生成树权值B的最大值.

        按贪心思想,应该是让B尽可能的小.对于A可以枚举每一条边,对于B是先求最小生成树的权值和.

        如果免费的边在最小生成树中 ans = max(ans,A/最小生成树的权值和-road[i].w)

        如果免费的边不在 ans = max(ans,A/最小生成树-maxn)  其中maxn 是枚举的边左右端点之间在最小生成树中权值最大的边.

        时间复杂度O(mlog₂m+m+n^₂)

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 1010;
 6 int h[N],idx,n,cnt,p[N];
 7 double sum,d1[N][N];
 8 struct Road{
 9     int fr,to,ne;
10     double w;
11 }road[N*N];
12 struct Path{
13     int u,v;
14     double w;
15     bool vis;
16     bool operator<(Path x){
17         return this->w<x.w;
18     }
19 }path[N*N];
20 struct Node{
21     int x,y,w;
22 }node[N];
23 void add(int a,int b,double c)
24 {
25     road[idx].w =c,road[idx].fr = a,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
26 }
27 double Getdist(Node s,Node e)
28 {
29     double dist = (s.x-e.x)*(s.x-e.x)+(s.y-e.y)*(s.y-e.y);
30     return sqrt(dist);
31 }
32 int findf(int x)
33 {
34     if(p[x]!=x) p[x] = findf(p[x]);
35     return p[x];
36 }
37 void dfs(int u,int fa,double max1,int gr)
38 {
39     d1[gr][u] = max1;
40     for(int i=h[u];~i;i=road[i].ne)
41     {
42         int v = road[i].to;
43         if(v==fa) continue;
44         double w = road[i].w;
45         dfs(v,u,max(w,max1),gr);
46     }
47 }
48 int main()
49 {
50     int T;
51     scanf("%d",&T);
52     while(T--)
53     {
54         scanf("%d",&n); idx = 0;
55         sum = 0; cnt = 0;
56         for(int i=1;i<=n;i++) scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w);
57         for(int i=1;i<=n;i++)
58           for(int j=1;j<=n;j++) d1[i][j] = 0;
59         for(int i=1;i<=n;i++){
60             p[i] = i,h[i] = -1;
61             for(int j=i+1;j<=n;j++){
62                 double s = Getdist(node[i],node[j]);
63                 path[++cnt] = {i,j,s,0};
64             }
65         }
66         sort(path+1,path+cnt+1);
67         for(int i=1;i<=cnt;i++)//构建最小生成树 
68         {
69             int pa = findf(path[i].u),pb = findf(path[i].v);
70             if(pa==pb) continue;
71             p[pa] = pb;
72             add(path[i].u,path[i].v,path[i].w);
73             add(path[i].v,path[i].u,path[i].w);
74             sum+=path[i].w;
75             path[i].vis = 1;
76         }
77         for(int i=1;i<=n;i++) dfs(i,-1,0,i);
78         double ans = 0;
79         for(int i=1;i<=cnt;i++)
80         {
81             int u = path[i].u,v = path[i].v;
82              int t = node[u].w+node[v].w;
83              if(path[i].vis) ans = max(t*1.0/(sum-path[i].w),ans);
84              else ans = max(t*1.0/(sum-d1[u][v]),ans);
85         }
86         printf("%.2lf\n",ans);
87     }
88     return 0;
89 }