训练指南 UVALive - 5713（最小生成树 + 次小生成树）

Diposting di | Edited on

Qin Shi Huang’s National Road System

UVALive - 5713

题意

有n个城市，要修一些路使得任意两个城市都能连通。但是有人答应可以不计成本的帮你修一条路，为了使成本最低，你要慎重选择修哪一条路。假设其余的道路长度为B，那条别人帮忙修的道路两端城市中的总人口为B，要找一个使A/B最大的方案。

题意

先求最小生成树，处理出MST中任意两点之间的最长边。因为别人只答应给修一条路，所以枚举这条路，用这条路替换下一条MST中最长的边（在加入这条路后构成的环中），比较求得A/B的最大值。实际上是把求次小生成树的一些后续操作改改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e3+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int n,m,x[maxn],y[maxn],p[maxn];

int pa[maxn];
int findset(int x){return pa[x]!=x?pa[x]=findset(pa[x]):x;}
vector<int>G[maxn];
vector<double>C[maxn];

struct Edge{
    int x,y;
    double d;
    bool operator < (const Edge& rhs)const{
        return d<rhs.d;
    }
};

Edge e[maxn*maxn];
double maxcost[maxn][maxn];
vector<int>nodes;

void dfs(int u,int fa,double facost){
    //cout<<"dfs="<<u<<endl;
    for(int i=0;i<nodes.size();i++){
        int x=nodes[i];
        maxcost[u][x]=maxcost[x][u]=max(maxcost[x][fa],facost);
    }
    nodes.push_back(u);
    for(int i=0;i<G[u].size();i++){
        if(G[u][i]==fa)continue;
        dfs(G[u][i],u,C[u][i]);
    }
}
double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
double MST(){
    m=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
    e[m++]=(Edge){i,j,dis(i,j)};
    sort(e,e+m);
    for(int i=0;i<n;i++){pa[i]=i;G[i].clear();C[i].clear();}
    int cnt=0;
    double ans=0;
    for(int i=0;i<m;i++){
        int x=e[i].x,y=e[i].y,u=findset(x),v=findset(y);
        double d=e[i].d;
        if(u==v)continue;
        pa[u]=v;
        G[x].push_back(y);G[y].push_back(x);
        C[x].push_back(d);C[y].push_back(d);
        ans+=d;
        if(++cnt==n-1)break;
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>x[i]>>y[i]>>p[i];
        double tot=MST();
        memset(maxcost,0,sizeof(maxcost));
        nodes.clear();
        dfs(0,-1,0);
        double ans=-1;
        for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++){
            ans=max(ans,(p[i]+p[j])/(tot-maxcost[i][j]));
        }
        cout<<fixed<<setprecision(2)<<ans<<endl;
    }
    return 0;
}