Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 排序后枚舉+kruskal 47ms

Posted by 1100012760 at 2012-08-03 21:33:24 on Problem 3522
```#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n , m , key[101] , mm;
bool flag;
struct edge
{
int l , m1 , m2;
}pp[5001];
int comp(const void* a , const void* b)
{
edge* p1 = (edge*)a;
edge* p2 = (edge*)b;
return p1->l-p2->l;
}
int fun(int a)
{
if(key[a]==a) return a;
key[a] = fun(key[a]);
return key[a];
}
int kruskal(int k)
{
int i , t = n-1 , p1 , p2;
for(i = 1 ; i <= n ; i++) key[i] = i;
for(i = k ; i <= m ; i++)
{
p1 = fun(pp[i].m1);
p2 = fun(pp[i].m2);
if(p1!=p2)
{
key[p1] = p2;
t--;
if(pp[i].l-pp[k].l>mm) return -1;
if(t==0)
return pp[i].l-pp[k].l;
}
}
return -1;
}
int main()
{
int a , b , l , i;
while(scanf("%d%d",&n,&m)&&n!=0)
{
flag = false;
for(i = 1 ; i <= m ; i++)
{
scanf("%d%d%d",&a,&b,&l);
pp[i].m1 = a;
pp[i].m2 = b;
pp[i].l = l;
}
qsort(pp+1,m,sizeof(edge),comp);
mm = 999999;
for(i = 1 ; m-i+1>=n-1 ; i++)
{
l = kruskal(i);
if(l!=-1&&l<mm)
{
mm = l;
flag = true;
}
while(i<m&&pp[i+1].l==pp[i].l)
i++;
}
if(!flag) printf("-1\n");
else printf("%d\n",mm);
}
return 0;
}
```

Followed by: