JDOJ 1044 Span

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

1

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[10010];
int cnt,n,m,tot;
int ans=2147483647;
struct rec
{
    int x,y,z;
}e[10010];
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=2147483647;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
        sort(e+1,e+m+1,cmp);
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
                fa[j]=j;
            cnt=0;
            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-1)
                    {
                        ans=min(ans,e[i].z-e[j].z);
                        break;
                    }
                }
            }
        }
        if(ans<2147483647)
            printf("%d
",ans);
        else
            printf("-1
");
    }
    return 0;
}