LA5713 秦始皇修路 （mst）

题意：

秦朝有n个城市，需要修路让每个城市都互相连通，现在可以免费修一条路，秦始皇希望他除了这条免费修的路外所需修的路的总和B最短，同时这条免费的路连接的人口之和A尽可能大，求最大的A/B是多少，城市之间的长度为欧几里得距离

思路：

这题是一个典型的最小生成树的题目。首先应该先求出最小生成树，其权值之和为W，然后再根据MST的回路性质，算出每一条路径对应的最大边权值，再进行遍历，求出最大的A/B即可

代码有参考这里

AC代码：

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <queue>

#include <map>

#include <vector>

#include <algorithm>

#include <bits/stdc++.h>

#include <iostream>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

const int maxn=;

struct Edge

{

    int a,b;

    double d;

    bool operator < (const Edge& rhs) const

    {

        return d < rhs.d;

    }

};

int x[maxn];

int y[maxn];

int p[maxn];

int n;

Edge e[maxn*maxn];

//G是与该节点相连的节点的编号，C是相应的cost

vector<int> G[maxn];

vector<double> C[maxn];

int par[maxn];

void init(){

    for(int i=;i<n;i++){

        par[i]=i;

        G[i].clear();

        C[i].clear();

    }

}

//int find(int x){return x==find(x)?x:par[x]=find(par[x]);}

int find(int x)

{

    if(x!=par[x])

        par[x] = find(par[x]);

    return par[x];

}

bool unite(int x,int y){

    x=find(x);

    y=find(y);

    if(x==y){

        return false;

    }else{

        par[x]=y;

        return true;

    }

}

double mst(){

    int cnt=;

    for(int i=;i<n;i++){

        for(int j=i+;j<n;j++){

            e[cnt].a=i;

            e[cnt].b=j;

            e[cnt].d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

            cnt++;

        }

    }

//    cout<<"ss"<<endl;

    sort(e,e+cnt);

    init();

    for(int i=; i<n; i++)

    {

        par[i] = i;

        G[i].clear();

        C[i].clear();

    }

    double ans=;

    int cnt2=;

//    cout<<"aa"<<endl;

    for(int i=;i<cnt;i++){

        if(unite(e[i].a,e[i].b)){

            G[e[i].a].push_back(e[i].b);

            C[e[i].a].push_back(e[i].d);

            G[e[i].b].push_back(e[i].a);

            C[e[i].b].push_back(e[i].d);

            ans+=e[i].d;

            cnt2++;

            if(cnt2==n-) break;

        }

    }

//    cout<<ans<<endl;

    return ans;

}

double costs[maxn][maxn];

vector<int> nodes;

//u是现在在搜索的节点，fa是u的父节点(从哪来)，facost是之前来的那条路的cost

void dfs(int u, int fa, double facost)

{

    for(int i = ; i < nodes.size(); i++)

    {

        int x = nodes[i];

        costs[u][x] = costs[x][u] = max(costs[x][fa], facost);

    }

    nodes.push_back(u);

    for(int i = ; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(v != fa)

            dfs(v, u, C[u][i]);

    }

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<n;i++){

            scanf("%d%d%d",&x[i],&y[i],&p[i]);

        }

//        cout<<"hh"<<endl;

        double total=mst();

        memset(costs,,sizeof(costs));

        nodes.clear();

        dfs(, -, );

        double ans = -;

        for(int i=; i<n; i++)

        {

            for(int j=i+; j<n; j++)

            {

                ans = max(ans,(p[i]+p[j])/(total-costs[i][j]));

            }

        }

        printf("%.2lf\n",ans);

    }

    return ;

}