UVa 1395 Slim Span【最小生成树】

时间:2023-03-08 16:33:08
UVa 1395 Slim Span【最小生成树】

题意:给出n个节点的图,求最大边减最小边尽量小的值的生成树

首先将边排序,然后枚举边的区间,判定在该区间内是否n个点连通,如果已经连通了,则构成一颗生成树,

则此时的苗条度是这个区间内最小的(和kruskal一样,如果在已经构成一颗树的基础上,再继续加入边,由于边都是排过序的,再加入的边一定会更大)

再维护一个最小值就好了

自己写的时候,枚举区间没有写对,然后判断1到n个点连通又写了一个for循环

后来看lrj的代码:发现是这样判断1到n是否连通的,每次枚举一个区间的时候,初始化cnt=n,当cnt=1时,说明已经加入了n-1条边,构成生成树了,那么此时已经连通

 #include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
const int INF = 0x7fffffff;
const int maxn=;
int p[maxn]; struct edge{
int v,u,w;
bool operator <(const edge& rhs) const{
return w<rhs.w;}
}; int find(int x){return p[x]==x? x:p[x]=find(p[x]);} int main(){
int n,m,i,j,ans;
while(scanf("%d %d",&n,&m)!=EOF&&n){
vector<edge> e;
edge ee;
for(i=;i<m;i++){
scanf("%d %d %d",&ee.v,&ee.u,&ee.w);
e.push_back(ee);
} sort(e.begin(),e.end()); int l,r;
ans=INF;
for(l=;l<m;l++){
int cnt=n;
for(i=;i<=n;i++) p[i]=i;
for(r=l;r<m;r++){
int x=find(e[r].v);
int y=find(e[r].u);
if(x!=y) {
p[x]=y;
cnt--;
if(cnt==) {
ans=min(ans,e[r].w-e[l].w);
break;
}
}
}
} if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
return ;
}

go---go---go--