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

时间：2022-12-15 07:11:21

layout: post

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

author: "luowentaoaa"

catalog: true

mathjax: true

tags:

- 最小生成树

- 图论

- 训练指南

Qin Shi Huang's National Road System

UVALive - 5713

题意

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

题意

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

#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;

}

相关文章