第一阶段（之三）

[珠浩 杨]

这是第三个算法了，希望我们大家都能够很好的去学习。

算法名字：最小生成树
完成时间：一周内
参与人员：杨珠浩，邱伟儒，邱志海

杨珠浩
2011年11月20日

[Qzi]

收到

2011/11/20 珠浩 杨 <clear...@gmail.com>

--
Your biological and technological distinctiveness will be added to our own. Resistance is futile.

[Qzi]

Reference :
Minimum_spanning_tree http://en.wikipedia.org/wiki/Minimum_spanning_tree
gdb 调试 http://wenku.baidu.com/view/17fe4e6db84ae45c3b358ce9.html
还是畅通工程 http://acm.hdu.edu.cn/showproblem.php?pid=1233
最小生成树(Minimum Spanning Tree) http://www.wutianqi.com/?p=1284

2011/11/24 Qzi <hotsea...@gmail.com>

[Qzi]

Minimum spanning tree

------------------------------------------------------------------------------------------------
| System  | CentOS Linux release 6.0 (Final)
------------------------------------------------------------------------------------------------
| Cimpiler | gcc version 4.4.4 20100726 (Red Hat 4.4.4-13) (GCC)
------------------------------------------------------------------------------------------------

HDU 1233 的解题主要的逻辑：
    int n;
    while(scanf("%d", &n) && n)
    {
        int m = n*(n-1)/2;
        memset(city, -1, sizeof(city));
        for(int i=0; i<m; ++i)
            scanf("%d %d %d", &road[i].c1, &road[i].c2, &road[i].cost);
        sort(road, road+m, myCompare);
        int sum = 0, count = 0;
        for(int i=0; i<m; ++i)
        {
            if(Merge(road[i].c1, road[i].c2))
            {
                count ++;
                sum += road[i].cost;
            }
            if(count == n-1)
                break;
        }
        printf("%d\n", sum);

    }



Reference :
Minimum_spanning_tree http://en.wikipedia.org/wiki/Minimum_spanning_tree
gdb 调试 http://wenku.baidu.com/view/17fe4e6db84ae45c3b358ce9.html
还是畅通工程 http://acm.hdu.edu.cn/showproblem.php?pid=1233
最小生成树(Minimum Spanning Tree) http://www.wutianqi.com/?p=1284

2011/11/27 Qzi <hotsea...@gmail.com>