AcWing 2069. 网络分析 -数据天堂

AcWing 2069. 网络分析

# windos 2024-04-03 09:09 0 16 来源：数据天堂

原题链接

考察:并查集

思路:

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

技术图片

这里有两种处理方式:

技术图片

一、建立虚点. 在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 <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N = 10010; 6 int p[N<<1],n,m,f[N<<1],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;i<=n*2;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<=n;i++)42  {43 if(p[i]!=i) f[i]+=f[findf(i)];44 printf("%d ",f[i]); 45  }46 return 0;47 }