首页 > 代码库 > uva1395 - Slim Span(最小生成树)

uva1395 - Slim Span(最小生成树)

先判断是不是连通图,不是就输出-1。

否则,把边排序,从最小的边开始枚举最小生成树里的最短边,对每个最短边用Kruskal算法找出最大边。

或者也可以不先判断连通图,而是在枚举之后如果ans还是INF,说明就没有,就输出-1.

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=100+10;int n,m,a,b;int p[maxn],used[maxn];struct Edge{    int u,v,w;}e[10000];vector<int>vv[maxn];bool cmp(const Edge& e1,const Edge& e2);void ini();int f(int x);void dfs(int t);int main(){    //freopen("in10.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(scanf("%d%d",&n,&m)==2)    {        if(n==0&&m==0) break;        ini();        for(int i=1;i<=m;i++)        {            scanf("%d%d%d",&a,&b,&e[i].w);            e[i].u=a;   e[i].v=b;            vv[a].push_back(b);            vv[b].push_back(a);        }        dfs(1);        bool lian=true;        for(int i=1;i<=n;i++)        {            if(used[i]==0)            {                lian=false;                break;            }        }        if(lian==false) puts("-1");//不是连通图,输出-1        else        {           sort(e+1,e+m+1,cmp);           if(m<n)           {               printf("%d\n",e[m].w-e[1].w);           }           else           {               int ans=INF;               for(int i=1;i<=m;i++)               {                   for(int k=1;k<=n;k++) p[k]=k;                   int num=0,ans_t;                   for(int j=i;j<=m;j++)                   {                       int x=f(e[j].u);                       int y=f(e[j].v);                       if(x!=y){num++; p[x]=y; ans_t=e[j].w;}                   }                   if(num==n-1)                   {                       ans=min(ans,ans_t-e[i].w);                   }               }               printf("%d\n",ans);           }        }    }    //fclose(stdin);    //fclose(stdout);    return 0;}bool cmp(const Edge& e1,const Edge& e2){    return e1.w<e2.w;}void ini(){    for(int i=0;i<=n;i++)    {        vv[i].clear();    }    memset(used,0,sizeof(used));}int f(int x){    return x==p[x]?x:p[x]=f(p[x]);}void dfs(int t){    used[t]=1;//记得进来以后要先标记上    int s=vv[t].size();    for(int i=0;i<s;i++)    {        int q=vv[t][i];        if(used[q]==0)        {            dfs(q);        }    }}

 

uva1395 - Slim Span(最小生成树)