JDOJ 1044 Span

https://neooj.com/oldoj/problem.php?id=1044

Description

　　某国有N个村子，M条道路，为了实现“村村通工程”现在要”油漆”N-1条道路（因为某些人总是说该国所有的项目全是从国外进口来的，只是漆上本国的油漆罢了），因为“和谐”是此国最大的目标和追求，以致于对于最小造价什么的都不在乎了，只希望你所选出来的最长边与最短边的差越小越好。

Input

　　第一行给出一个数字TOT，代表有多少组数据,Tot<=6 　　对于每组数据，首先给出N，M 　　下面M行，每行三个数a,b,c代表a村与b的村道路距离为c.

Output

　　输出最小差值,如果无解输出”-1”.

Sample Input

1 4 5 1 2 3 1 3 5 1 4 6 2 4 6 3 4 7

Sample Output

HINT

【样例解释】　　选择1-4,2-4,3-4这三条边. 【数据范围】　　1:2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2 　　2:每条边的权值小于等于10000 　　3:保证没有自环，没有重边

不要把这道题想象成最小生成树的练习题，虽然原理跟最小生成树很像，但是题目中明确要求不要求最小造价，所以我们的解决办法是，使用kruskal算法排序后，从小到大枚举每条边，每次都跑最小生成树，然后更新ans为最长边与最短边差的最小值。

Code:

#include<cstdio>

#include<algorithm>

using namespace std;

int fa[];

int cnt,n,m,tot;

int ans=;

struct rec

{

    int x,y,z;

}e[];

bool cmp(rec a,rec b)

{

    return a.z>b.z;

}

int find(int x)

{

    if(fa[x]==x)    return x;

    return fa[x]=find(fa[x]);

}

int main()

{

    scanf("%d",&tot);

    while(tot--)

    {

        ans=;

        scanf("%d%d",&n,&m);

        for(int i=;i<=m;i++)

            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);

        sort(e+,e+m+,cmp);

        for(int i=;i<=m;i++)

        {

            for(int j=;j<=n;j++)

                fa[j]=j;

            cnt=;

            for(int j=i;j<=m;j++)

            {

                int fx=find(e[j].x);

                int fy=find(e[j].y);

                if(fx!=fy)

                {

                    fa[fx]=fy;

                    cnt++;

                    if(cnt==n-)

                    {

                        ans=min(ans,e[i].z-e[j].z);

                        break;

                    }

                }

            }

        }

        if(ans<)

            printf("%d\n",ans);

        else

            printf("-1\n");

    }

    return ;

}

巴特西