【图论杂题】：H.loser [最小生成树+并查集]

题目：

团队链接：loser

题面：

给定一个$n$个点的带点权带边权完全图
请你取出图中的一棵树来，再选出两个点，树上的一条边满足

• 两点在树上的路径经过该边
• 定义$A$为两个点的点权和
• 定义$B$为树上未选中边的边权和
  求$\frac{A}{B}$的最大值

范围：$n<=1000$

输入格式：

（这是一个坐标系！！！）
第一行输入n，第2到n+1行输入第i个点的信息：坐标（x，y）和点权。
边权为坐标系上两点之间的距离。

输出格式：

$\frac{A}{B}$的最大值（结果保留两位小数即可）

样例：

输入：

5
3 5 71
567 2 64
69 3 100
768 2 47
460 3 96

输出：

0.52

题解：

由于求的是$\frac{A}{B}$的最大值，所以要让B尽量小，A尽量大，所以从图中抠出来的树很显然就是整个图的最小生成树（这样B尽量小），然后在求最小生成树的图中对于点权跑个并查集记录一下最大点权即可。

代码：

#include<bits/stdc++.h>
#define D double
using namespace std;
inline int read()
{
    int s=0,w=1; char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e6+7;
const int pool=1e3+7;
struct see{
    int ver,x; D edge;}e[sea];
int n,tot=0,cnt=0,x[pool],y[pool],w[pool],fa[pool],mx[pool];
D ans,ans1[pool],ans2[pool],sum;
D dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));} 
void add(int x,int y,D z){
    e[++tot].x=x;e[tot].ver=y;e[tot].edge=z;}
bool cmp(see x,see y){
    return x.edge<y.edge;}
int get(int x){
    if(x==fa[x]) return x;else return fa[x]=get(fa[x]);}
int main()
{
    n=read();for(int i=1;i<=n;i++) x[i]=read(),y[i]=read(),w[i]=read();for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) add(i,j,dis(i,j));for(int i=1;i<=n;i++) fa[i]=i,mx[i]=w[i];sort(e+1,e+1+tot,cmp);for(int i=1;i<=tot;i++){
    int x=get(e[i].x),y=get(e[i].ver);if(x==y) continue; sum+=e[i].edge;ans1[++cnt]=mx[x]+mx[y]; ans2[cnt]=e[i].edge; fa[x]=y; mx[y]=max(mx[x],mx[y]);if(cnt==n-1) break;}for(int i=1;i<n;i++) ans=max(ans,ans1[i]/(sum-ans2[i]));printf("%.2f\n",ans);return 0;
}

Continue……