3

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

问题定义：

鲍勃在学校旅行期间参观了一座核电站。他观察到工厂中有 n 根核棒，核棒的初始效率为 1。一段时间后，核棒开始相互融合并结合形成一个群。这个过程将核棒的效率降低到组大小的平方根。Bob 是一个好奇的学生，他想知道一段时间后核电站的总效率。这是通过增加组的效率来获得的。

最初所有的棒都属于它自己的大小为 1 的组。有 f 个融合。如果 rod1 和 rod2 融合，则意味着它们的组融合了。

样本输入：

5 2

1 2

2 3

样本输出：

3.73

解释：

n=5 融合=2

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

第 4 组 => 1

第 5 组 => 1

总计 = (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

我真的无法弄清楚我哪里出错了，因为输入真的很大。

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

4

1 回答 1

1

p持有元素的直接父母，而不是他们的findSet价值观。因此，当您这样做时，set<lli> s (p.begin(),p.end());您可以在其中添加其他元素。

我可以想到两种方法来处理这个问题：

  1. 使用循环将 findSet(i) 插入集合中，而不是直接放入 p
  2. 完成后setSize[i] += setSize[j]，设置setSize[j] = 0。这样，中间父母不会对总和做出贡献。
于 2017-01-21T10:17:58.457 回答