uva1395 苗条的生成树

并查集+最小生成树水题

暴力枚举即可

链接：https://www.luogu.com.cn/problem/UVA1395

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<math.h>
#define ll long long
using namespace std;
const int maxn=1000;
const int mod=1e9;
int fa[maxn],tree[maxn];
struct node{
      int u,v,w;
      bool operator <(const node&ch)const
      {
          return w<ch.w;
      }
}a[maxn];

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void Union(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx!=fy)
        fa[fx]=fy;
    return ;
}
void solve(int n,int m)
{

    for(int i=1; i<=m; i++) cin>>a[i].u>>a[i].v>>a[i].w;
    sort(a+1,a+1+m);
    //for(int i=1; i<=m; i++)
        //cout<<a[i].u<<a[i].v<<a[i].w<<endl;
    int flag=0,cot;
    int minn=0x3f3f3f3f;
    for(int i=1; i<=m; i++)
    {
        cot=0;
        for(int k=1; k<=maxn-5; k++) fa[k]=k;
        for(int j=i; j<=m; j++)
        {
            if(find(a[j].u!=find(a[j].v)))
            {
                tree[++cot]=j;
                Union(a[j].u,a[j].v);
                if(cot==n-1)
                 break;
            }
        }
        if(cot==n-1)
        {
            //for(int h=1; h<=cot; h++) cout<<tree[h]<<" ";
            flag=1;
            minn=min(a[tree[cot]].w-a[tree[1]].w,minn);
            //cout<<minn<<" ";
        }
    }
    //cout<<cot;
    if(flag)
        printf("%d
",minn);
    else
        printf("-1
");

}
int main()
{
    int n,m;
    while(cin>>n>>m&&n&&m)
        solve(n,m);
    return 0;}