关于#java#的问题：3.每个顶点的点权不小于初始时的 p/q​求最小的 x≥1，均存在一种满足上述要求的重新分配方式

Question

求指教，给出求解的源代码，感激不尽

题意简述
给定一个 n个顶点 m 条边的无向图，可能有重边自环，可能不连通。
初始时每个顶点有点权，点权为随机正实数。现在需要重新分配每个顶点的点权，使得：
1.相邻顶点的点权中较大者与较小者之比不超过 x；
2.点权总和不变；
3.每个顶点的点权不小于初始时的 p/q
​求最小的 x≥1，使得对于给定的图，无论初始点权如何，均存在一种满足上述要求的重新分配方式。

Answer 1

Kruskal 算法的思想是: 先将所有的边按从小到大的顺序进行排序,排完序之后从小到大的遍历一遍所有的边,如果当前遍历到的边的两端的端点不是连通的,也就是不在一个集合中的话,就加入这条边。

因为如果一条边的两个端点不是连通的,为了使他连通的话,加入当前边的代价是最小的,因为之前对所有的边进行了从小到大的排序了。

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[100010];
 
struct Edge{
    int a;
    int b;
    int w;
    bool operator < (const Edge& c)const{
        return w < c.w;
    }
}edge[200010];
 
int find(int x){
    if (p[x] != x){
        p[x] = find(p[x]);
    }
    return p[x];
}
 
int main(){
    int n,m,a,x,y,w;
    cin>>n>>m;
    for (int i = 0 ; i < m; i++){
        scanf("%d%d%d",&x,&y,&w);
        edge[i] = {x,y,w};
    }
    
    sort(edge,edge + m);
    
    for (int i = 1 ; i <= n; ++i) p[i] = i;  //并查集的初始化操作,使得每个点的父亲结点都是自己
    
    int res = 0,cnt = 0;
    
    for (int i = 0; i < m; ++i){
        int x = edge[i].a;
        int y = edge[i].b;
        int ww = edge[i].w;
        int px = find(x);
        int py = find(y);
        if (px != py){
            cnt ++;
            res += ww;
            p[px] = py;
        }
    }
    if (cnt < n - 1) puts("impossible");
    else cout<<res<<endl;
    return 0;
}