c++ - C++ 中的不相交集实现

Question

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

问题定义:

Bob visits a nuclear power plant during his school excursion. He observes that there are n nuclear rods in the plant and the initial efficiency of the nuclear rods is 1. After a period of time nuclear rods start fusing with each other and combine to form a group. This process reduces the efficiency of the nuclear rods to square root of the size of the group. Bob, being a curious student, wants to know the total efficiency of the nuclear plant after some time. This is obtained by adding the efficiencies of the groups.

Initially all the rods belong to its own group of size 1. There are f fusions. If rod1 and rod2 get fused, it means their groups got fused.

示例输入:

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.
}

上面的代码似乎适用于除一个以外的所有测试用例。

输入是here我的代码失败了。

预期的输出是:67484.82

我的输出:67912.32

我真的不知道哪里出了问题，因为输入量实在是太大了。

任何帮助将不胜感激。提前致谢。

Answer 1

p持有元素的直接父代而不是它们的 findSet值。因此当你做 set<lli> s (p.begin(),p.end());你可以在那里有额外的元素。

有两种方法可以解决这个问题:

1. 用循环将findSet(i)插入set中而不是直接放入p
2. 在你做完之后setSize[i] += setSize[j] , 设置 setSize[j] = 0 .这样，中间 parent 就不会贡献总和。