AcWing 2069. 网络分析

2021-05-15 20:30

阅读：757

标签：ret width 路径压缩 ++ 合并传递 const cst 并查集

原题链接

考察:并查集

思路:

很容易想到用并查集的根节点代表此集合的权值和.但是注意在结点合并的时候,会出现本不属于这里的权值.被路径压缩加到子结点上.

技术图片

这里有两种处理方式:

技术图片

一、建立虚点. 在x,y之上建立一个结点s,在路径压缩时就不会合并到y集合的权值k.

二、特殊处理x结点权值,在x权值和上减去y的权值和.

但是注意:直接这么路径压缩会使得1 2 4(样例)权值和计算错误.我们第一次合并可能会将r,p[x]的权值传递给x,但后面查询x的父节点后,又会将r的权值和再累加到x里.所以根据并查集压缩路径的结果,当枝条结点只有两个时,我们不进行权值合并,那么最后x的权值和结果是f[x]+f[p[x]].如果>2个,要符合前面的算式我们需要f[x] = f[x]+f[p[x]]因此路径压缩时可以累加父节点的权值.

最后还有一种特殊情况,就是p[x] = x.此时累加会使得结果重复.

技术图片

 1 #include  2 #include  3 #include 
 4 using namespace std;
 5 const int N = 10010;
 6 int p[N1],n,m,f[N1],idx;
 7 int findf(int x)
 8 {
 9     if(x!=p[x])
10     {
11         int pa = findf(p[x]);
12         if(pa!=p[x]) f[x]+=f[p[x]];
13         p[x] = pa;
14     }
15     return p[x];
16 }
17 void merge(int a,int b)
18 {
19     int pa = findf(a),pb = findf(b);
20     if(pa==pb) return;
21     p[pa] = ++idx;
22     p[pb] = idx;
23 }
24 void add(int x,int score)
25 {
26     int pa = findf(x);
27     f[pa]+=score;
28 }
29 int main()
30 {
31     scanf("%d%d",&n,&m);
32     idx = n;
33     for(int i=1;i2;i++) p[i] = i;
34     while(m--)
35     {
36         int op,x,y;
37         scanf("%d%d%d",&op,&x,&y);
38         if(op==1) merge(x,y);
39         else add(x,y);
40     }
41     for(int i=1;i)
42     {
43         if(p[i]!=i) f[i]+=f[findf(i)];
44         printf("%d ",f[i]); 
45     }
46     return 0;
47 }

AcWing 2069. 网络分析

标签：ret width 路径压缩 ++ 合并传递 const cst 并查集

原文地址：https://www.cnblogs.com/newblg/p/14665350.html

上一篇：windows配置redis cluster

下一篇：python构造二维列表以及排序字典

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 2069. 网络分析
文章链接：http://soscw.com/index.php/essay/85950.html

亲，登录后才可以留言！

AcWing 2069. 网络分析

评论

热门文章

推荐文章

最新文章

置顶文章