#include<stdio.h>

#include<string.h>

int father[105],depth[105];

int dist[105],map[101][101];

int vis[105],n;

void init_B()

{

    int i;

    for(i = 1;i <= n;i ++)

    {

        father[i] = i;

        depth[i] = 0;

    }

}

int find(int x)

{

    if(x == father[x])

        return x;

    return father[x] = find(father[x]);

}

void unit(int x,int y)

{

    x = find(x);

    y = find(y);

    if(x == y)

        return ;

    if(depth[x] < depth[y])

        father[x] = y;

    else

    {

        if(depth[x] > depth[y])

            father[y] = x;

        else

        {

            father[x] = y;

            depth[y]++;

        }

    }

}

void init()

{

    int i;

    memset(vis,0,sizeof(vis));

    for(i = 1;i <= n;i ++)

        dist[i] = map[1][i];

}

int main()

{

    int m,i,j,k,a,b;

    int min,cnt,cost,sum;

    while(~scanf("%d%d",&m,&n) && m)

    {

        init_B();

        sum = cnt = 0;

        for(i = 1;i <= n;i ++)

        {

            for(j = 1;j <= n;j ++)

            {

                if(i != j)

                {

                    map[i][j] = 1 << 30;

                }

            }

        }

        while(m--)

        {

            scanf("%d%d%d",&a,&b,&cost);

            map[a][b] = map[b][a] = cost;

            unit(a,b);

        }

        init();

        for(i = 1;i <= n;i ++)

        {

            if(i == find(i))

                cnt++;

            if(cnt == 2)

                break ;

        }

        if(cnt == 2)

        {

            printf("?\n");

            continue ;

        }

        for(i = 0;i < n;i ++)

        {

            min = 1 << 30;

            for(j = 1;j <= n;j ++)

            {

                if(!vis[j] && min > dist[j])

                {

                    min = dist[j];

                    k = j;

                }

            }

            vis[k] = 1;

            if(min != 1 << 30)

                sum += min;

            for(j = 1;j <= n;j ++)

            {

                if(!vis[j] && dist[j] > map[k][j])

                    dist[j] = map[k][j];

            }

        }

        printf("%d\n",sum);

    }

    return 0;

}

最新文章

1. c#中字段和属性的区别
2. 使用TopSelf创建自宿主的Windows服务程序
3. SWF READER 破解日志。
4. 查找SQL数据表或视图中的字段属性信息
5. python 自动生成C++代码 （代码生成器）
6. Spring入门Hello World
7. 关于在VMware上装lFEDORA系统
8. 时尚B2B方兴未艾－Maker’s Row 获100万美元种子投资 |华丽志
9. 非PE病毒介绍
10. sum,filter和map参数里面的玄机
11. ROS_Kinetic_04 ROS基础内容（一）
12. java使用类数组 报错Exception in thread "main" java.lang.NullPointerException
13. jQuery学习之二
14. PPT 遥控器
15. CentOS6.8 x64+Nginx1.3.8/Apache-httpd 2.4.3+PHP5.4.8(php-fpm)+MySQL5.5.28+CoreSeek4.1源码编译安装
16. Python学习-3.Python的模块加载
17. android之截屏(包括截取scrollview与listview的)
18. infopath 2007 升级到2013 栏目字段重复生成问题
19. Hexo博客搭建全解
20. angular Dom属性绑定

热门文章

1. C# 解析带前缀的Xml节点内容
2. 会话控制：cookie和session基础学习笔记
3. grep线上环境精典案例后续
4. [转]LoadRunner脚本录制常见问题整理
5. ibatis访问oracle数据库US7ASCII中文乱码问题
6. Extjs4.2 多选下拉框
7. use worker without js file
8. Python编程规范及性能优化（转载）
9. Js通过原型继承创建子类
10. web网页前端制作中的SEO方法