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, 每次更新最小值即可，一次AC,估计把样例过了就能ac,AC代码见下

Posted by su03121231 at 2013-07-29 15:27:53 on Problem 3522
```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
typedef struct
{
int x;
int y;
int w;
}init;
int cmp(const void *a, const void *b)
{
init *c=(init *)a;
init *d=(init *)b;
return c->w - d->w;
}
int p[105];
void set()
{
for(int i=0;i<105;i++)
p[i]=i;
}
int find(int x)
{
int s=x;
while(s!=p[x])
{
s=p[x];
x=p[s];
}
return p[x];
}
int main()
{
int n,m,i,j,min,flag,t,count;
init map[5005];
while(scanf("%d%d",&n,&m),n+m)
{
memset(map,0,sizeof(map));
min=INT_MAX;
flag=0;

for(i=0;i<m;i++)
{
scanf("%d%d%d",&map[i].x,&map[i].y,&map[i].w);
}
qsort(map,5005,sizeof(map[0]),cmp);
for(i=0;!map[i].w;i++);
for(t=0;t<m-n+2;t++)
{
set();
for(j=i,count=0;j<5005;j++)
{
int f1=find(map[j].x);
int f2=find(map[j].y);
if(f1 != f2)
{
p[f1]=f2;
count++;
}
if(count == n-1)
{
flag=1;
if(map[j].w - map[i].w <min)
min=map[j].w - map[i].w;
i++;
break;
}
}
}
if(flag)
printf("%d\n",min);
else
printf("-1\n");
}
return 0;
}```

Followed by: