题目描述

给出n条从x到y的限速为z的路，求从一个点到另一个点的最的限速和最小限速中比值最小的值

思路

排序后每次从一个点出发，一直玩并差集中塞数，塞到两点连通为止，然后判断一下就可以了
O(n^2)
这里在判断比值大小的时候不可以用int直接“/”，而是要变为实型再除

#include 
#include 
#include 
using namespace std;
int f[100000];
struct arr
{
    int x,y,z;
};
arr a[100000];
int n,m;
int cam(arr a,arr b)
{
    return a.z>b.z;
}
int find(int x)
{
    if (f[x]==0) return x;
    f[x]=find(f[x]);
    return f[x];
}
int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int gcd(int x,int y)
{
     if(y==0) return x;    
     if(xl1/r1)
        {
            fl=1;
            minx=l;
            miny=r;
        }
    }
    if (!fl)
        printf("IMPOSSIBLE");
    else 
    {   
        int d=gcd(minx,miny);
        minx=minx/d;
        miny=miny/d;
        if (minx%miny==0) printf("%d\n",minx/miny);
        else printf("%d/%d\n",minx,miny);
    }

}