Kruskal算法解决POJ 1861

深碍√TFBOYSˉ_ 2021-11-11 11:48 235阅读 0赞

题目：http://poj.org/problem?id=1861

说下题意，给出节点个数m和边数n，下面n行给出边(x,y)以及权值w。

输出第一行为最小生成树中的最大边权值，第二行为一个可行生成树方案的边数k，

下面k行为可行生成树的k条边。

题目是Special Judge，意思就是不具有唯一解，可能有多解，

样例输出为以下结果也可算对。

1  
3  
1 3  
2 4  
2 3

一样按照Kruskal解题即可，结果虽然不唯一，但是最小生成树一定是可行解之一。

将边加入生成树时记录最大权值和边信息然后输出即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include "iostream"
    #include "algorithm"
    using namespace std;
    structline
    {
        int begin;
        int end;
        int length;
    };
    line Num[15001];
    line Store[15001];
    int father[1001], map[1001][1001], i, j, numofline, numofnode, counter;
    int find(int k)
    {
        return father[k]==k?k:father[k]=find(father[k]);
    }
    int cmp(line a, line b)
    {
        return a.length<b.length;
    }
    void kruskal()
    {
        counter = 0;
        int a, b, c, d, l;
        for(i=0; i<numofline; i++)
        {
                    c = Num[i].begin;  //记录改变前的begin结点
            d = Num[i].end;  //记录改变前的edc结点
            l = Num[i].length;  //记录改变前的length结点
            a = find(Num[i].begin);  
            b = find(Num[i].end);
            if(a!=b)
            {
                Store[counter].length = l;  //存储length
                Store[counter].begin = c;  //存储begin
                Store[counter++].end = d;  //存储end
                father[a] = b;
            }
    
                    //然而，我发现没有必要去记录改变前的begin,end,length等的值，
    
                    //因为，它们从来都没有改变过，改变的只是对应的father中的值。
    
                    //对于，这个的纠正就是说明我更加理解了并查集了。
        }
    }
    void Init()
    {
        cin>>numofnode>>numofline;
        for(i=1; i<=numofnode; i++)
            father[i] = i;
        for(i=0; i<numofline; i++)
            cin>>Num[i].begin>>Num[i].end>>Num[i].length;
        sort(Num, Num+numofline, cmp);
    }
    int main()
    {
        Init();
        kruskal();
        cout<<Store[counter-1].length<<endl;
        cout<<counter<<endl;
        for(i=0; i<counter; i++)
            cout<<Store[i].begin<<" "<<Store[i].end<<endl;
    }

转载于:https://www.cnblogs.com/o8le/archive/2011/09/23/2186730.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/2595efd32c9a494ea340656fb650e7d9.png