首页 > 其他 > 详细

poj 3522 Slim Span 最大边减最小边最小的生成树

时间:2014-07-12 14:37:35      阅读:423      评论:0      收藏:0      [点我收藏+]

枚举最小边进行kruskal。

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 120
#define maxm 10000
struct edge
{
    int u,v,w;
}e[maxm];
int p[maxn],n,m;
int find(int x)
{
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}
void link(int a,int b)
{
    int fa=find(a);
    int fb=find(b);
    if(fa!=fb)
        p[fa]=fb;
}
int cmp(const void *a,const void *b)
{
    edge aa=*(const edge*)a;
    edge bb=*(const edge*)b;
    return aa.w-bb.w;
}
int main()
{
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(n+m==0) break;
        int i,j;
        int u,v,w;
        int l,r;
        for(i=0;i<m;i++)
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
        qsort(e,m,sizeof(e[0]),cmp);
        int minn=10000000;
        for(l=0;l<m;l++)
        {
            int num=0;
            for(i=1;i<=n;i++) p[i]=i;
            for(i=l;i<m;i++)
            {
                u=e[i].u;
                v=e[i].v;
                w=e[i].w;
                if(find(u)!=find(v))
                {
                    link(u,v);
                    r=w;
                    num++;
                }
            }
            if(num==(n-1)&&(r-e[l].w)<minn)
                minn=r-e[l].w;
        }
        if(minn==10000000) printf("-1\n");
        else printf("%d\n",minn);
    }
    return 0;
}

 

poj 3522 Slim Span 最大边减最小边最小的生成树,布布扣,bubuko.com

poj 3522 Slim Span 最大边减最小边最小的生成树

原文:http://www.cnblogs.com/vermouth/p/3839930.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!