最小差值生成树求助
查看原帖
最小差值生成树求助
270854
二叉苹果树楼主2022/8/22 11:43

rt,应该是求最小生成树的地方写错了

#include<iostream>
#include<algorithm>
using namespace std;
int f[100005];
int find(int x)
{
    if (f[x]==x)
        return x;
    else
        {
            f[x]=find(f[x]);
            return f[x];
        }
}
struct edge
{
    int u,v,w;
    bool operator<(const edge& e) const
    {
        return w<e.w;
    }
}a[200005];
int n,m,Min;
int cnt;

int main()
{
    while(1)
    {
        cin>>n>>m;
        if(n==m&&m==0)
            break;
        Min=0x7fffffff;
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=1;i<=m;i++)
            cin>>a[i].u>>a[i].v>>a[i].w;
        sort(a+1,a+m+1);
        for(int i=1;i<=m-n+1+1;i++)
            for(int j=i;j<=m;j++)
            if(find(a[i].u)!=find(a[i].v))
            {
                f[find(a[i].u)]=find(a[i].v);
                cnt++;
                if(cnt==n-1)
                {
                    if(a[j].w-a[i].w<Min)
                        Min=a[j].w-a[i].w;
                    break;
                }
            }
        if(cnt<n-1)
            cout<<"-1"<<endl;
        else
            cout<<Min<<endl;
        }
    return 0;
}
2022/8/22 11:43
加载中...