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

## Kruscal+枚举

Posted by 2015110720 at 2018-07-05 19:22:53 on Problem 3522
```#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
/*
Kruscal加上枚举，枚举第一个加入生成树的边
（从小到大）
*/
const int maxn=105;
const int maxm=5005;
const int INF=10010;

struct edge
{
int u,v,w;
}e[maxm];

int n,m;
int pre[maxn];

int cmp(edge a,edge b)
{
return a.w<b.w;
}

int find(int x)//并查集找到树根
{
int r=x;
while(r!=pre[r])r=pre[r];
int i=x,j;
while(i!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}

int min(int a,int b)
{
return (a<b)?a:b;
}

int max(int a,int b)
{
return (a>b)?a:b;
}

int kruscal(int x)
{
int big=0,small=10005,count=0;
for(int i=x;i<m;i++)
{
int u=e[i].u,v=e[i].v,w=e[i].w;
int gu=find(u),gv=find(v);
if(gu!=gv)
{
pre[gu]=gv;
big=max(big,w);
small=min(small,w);
count++;
}
if(count>=n-1)break;
}
if(count>=n-1)return (big-small);
else return INF;
}

int main()
{
while(cin>>n>>m)
{
if(n==0 && m==0)break;
for(int i=0;i<m;i++)
{
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e,e+m,cmp);

int res=INF;

for(int i=0;i<m;i++)
{
for(int j=1;j<=n;j++)pre[j]=j;
res=min(res,kruscal(i));
}

if(res==INF)cout<<-1<<endl;
else cout<<res<<endl;
}
return 0;
}```

Followed by: