# Poj Solution 3522

```http://poj.org/problem?id=3522

//* @author:
import java.io.*;
import java.util.*;
/*�����������Ȩֵ����СȨֵ����С��:
*��˼��:�ȶԱ�����. ���������ڵ�һ����������,��¼���Ȩֵ����СȨֵ����С��,ö���������
*��α�֤�������������Ž���,��Ϊ���Ѿ���Ȩֵ��������,���ڵ�һ�����ɵ����Ȼ����С��(�Ͻ���½�֮����С)
*/
class cin
{
static int a,c;
static int nextInt() throws IOException
{
a=0;
while(c!=' '&&c!='r'&&c!='n')
{
a=a*10+c-'0';
}
return a;
}
}

class E
{
int weight,from,to;
void init(int x,int y,int z)
{
weight=z;
from=x;
to=y;
}
}

class Cmp implements Comparator
{
public int compare(Object a,Object b)
{
int c=((E)a).weight-((E)b).weight;
if(c< 0)return -1;
return 1;
}
}

class Set
{
int father[];
int num;
Set(int n)
{
num=n;
father=new int[n+1];
this.clear();
}

void clear()
{
int i;
num=father.length-1;
for(i=1;i<=num;i++)father[i]=i;
}

int findF(int x)
{
int t=x;
while(t!=father[t])
{
t=father[t];
}
while(x!=father[x])
{
father[x]=t;
x=father[x];
}
return t;
}

boolean union(int x,int y)
{
int fx=findF(x),fy=findF(y);
if(fx==fy)return false;
father[fy]=fx;
num--;
return true;
}
}

class Kruskal
{
E e[];
int numOfE,numOfTree,i,j,numOfD;
Set points;

Kruskal(E a[],int m,int n)
{
e=a;
numOfE=m;
numOfD=n;
points=new Set(numOfD);
}

int cost()
{
int dis=100000,h,k=0;
Arrays.sort(e,new Cmp());
for(i=0;i< numOfE;i++)    //��Ҫ���ִ���
{
if(points.union(e[i].from,e[i].to))
{
if(points.num==1)   //���һ����
{
k++;
while(true)
{
points.clear();
for(h=k;h<=i;h++)
{
points.union(e[h].from, e[h].to);
}
if(points.num==1)k++; //ȥ���Ҫ�ı�
else break;
}
if(dis>e[i].weight-e[k-1].weight) //���㲢������С��ֵ
dis=e[i].weight-e[k-1].weight;
}
}
}
if(dis==100000)dis=-1;
return dis;
}

}

public class Main {
public static void main(String args[]) throws IOException
{
int n,m,i;
E e[];
while(true)
{
n=cin.nextInt();
m=cin.nextInt();
if(n==0&&m==0)break;
e=new E[m];
for(i=0;i< m;i++)
{
e[i]=new E();
e[i].init(cin.nextInt(), cin.nextInt(), cin.nextInt());
}
Kruskal data=new Kruskal(e,m,n);
System.out.println(data.cost());
}
}
}
```
This entry was posted in poj. Bookmark the permalink.