C++中的不相交集合实现

Question

C++中的不相交集合实现

3

我在一场在线比赛中遇到了这个问题，我正在尝试使用不相交集数据结构来解决它。

问题定义：

Bob参观了一个核电站，在他的学校研究中心。他观察到该电站有n个核棒，核棒的初始效率为1。经过一段时间，核棒开始融合，组成一个群体。这个过程会将核棒的效率降低到该群体大小的平方根。作为一个好奇的学生，Bob想知道一段时间后核电站的总效率。这是通过添加群体的效率来获得的。

最初，所有的棒子都属于自己的大小为1的群体。有f个融合。如果棒1和棒2融合，那么它们的群体也融合了。

样例输入:

5 2

1 2

2 3

样例输出:

3.73

解释：

n=5 fusions=2

group 1,2,3 => 1.73 (sqrt(3))

group 4 => 1

group 5 => 1

total = (1.73 + 1 + 1) = 3.73

我的代码：

#include <iostream>
#include <set>
#include <vector>
#include <stdio.h>
#include <math.h>
#include <iomanip>
using namespace std;

typedef long long int lli;

vector<lli> p,rank1,setSize;   /* p keeps track of the parent
                                * rank1 keeps track of the rank
                                * setSize keeps track of the size of the set. 
                                */ 

lli findSet(lli i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); } 

bool sameSet(lli x,lli y) { return findSet(x) == findSet(y); }


void union1(lli x,lli y) {      // union merges two sets.

    if(!sameSet(x,y)) {

        lli i = findSet(x), j = findSet(y);

        if(rank1[i] > rank1[j]) {
            p[j] = i;
            setSize[i] += setSize[j];           

        }

        else {
            p[i] = j;
            setSize[j] += setSize[i];
            if(rank1[i] == rank1[j])
                rank1[j]++;
        }
    }
}

int main() {

    freopen("input","r",stdin);

    lli n;
    cin >> n;                               //number of nuclear rods

    setSize.assign(n,1);                    //Initialize the setSize with 1 because every element is in its own set
    p.assign(n,0);          
    rank1.assign(n,0);                      //Initialize ranks with 0's.

    for(lli i = 0; i < n; i++) p[i] = i;    //Every set is distinct. Thus it is its own parent.

    lli f;
    cin >> f;                               //Number of fusions.

    while(f--){                 

        lli x,y;
        cin >> x >> y;                      //combine two rods
        union1(x,y);                        

    }   

    double ans; 

    set<lli> s (p.begin(),p.end());         //Get the representative of all the sets.

    for(lli i : s){     
        ans += sqrt(setSize[i]);            //sum the sqrt of all the members of that set.

    }

    printf("\n%.2f", ans);                  //display the answer in 2 decimal places.
}

上述代码似乎对所有测试用例都有效，但有一个测试用例无法通过。

输入在这里，我的代码无法通过此测试用例。

期望输出为：67484.82

我的输出为：67912.32

由于输入数据非常大，我真的搞不清楚哪里出了问题。

如有帮助，将不胜感激。先行致谢。

- Raghav

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Raziman T V · Accepted Answer

p保存的是元素的直接父节点，而不是它们的findSet值。因此当你执行set<lli> s (p.begin(),p.end());时，可能会有额外的元素存在。

我能想到两种处理方法：

使用循环将findSet(i)插入集合中，而不是直接放置p
在执行setSize[i] += setSize[j]后，设置setSize[j] = 0。这样，中间的父节点将不会对总和产生贡献。