網絡分析

題意：

有n個節點，一開始彼此獨立，有兩個操作，第一個操作時是連接兩個節點，第二個操作是對一個節點+x，（在進行第二個操作時，與該點相連的點也會+x）
問每個節點的權值

題解：

帶權并查集
我所理解的帶權并查集是這樣的，就是把所有權值全部加到父親節點，在路徑壓縮的情況下，一個并查集里的權值全部移動到根節點，相當于整個并查集共享整個權值，但是有的節點是在其他節點被加后再加入并查集的，也就是共享的并查集并不全歸子節點，所以子節點x的值為d[px]=value[px] - value[py]
px為x的根節點，py為y的根節點，x與y相連
數組value[x]表示以x為根節點的并查集共享的權值
數組d[x]表示x節點相對于根節點的權值的差值

代碼：

#include <iostream> using namespace std; const int N = 4E4 + 10; int parent[N], value[N], d[N]; int n, m; int find(int x){if(parent[x] != x){int root = find(parent[x]);d[x] += d[parent[x]];parent[x] = root;}return parent[x]; } int main(){cin >> n >> m;for(int i = 1; i <= n; i ++ ) parent[i] = i;while(m -- ){int op, x, y; cin >> op >> x >> y;if(op == 1){int px = find(x), py = find(y);if(px == py) continue;d[px] += value[px] - value[py];parent[px] = py;}else{int px = find(x);value[px] += y;}}for(int i = 1; i <= n; i ++ ) cout << value[find(i)] + d[i] << ' ';return 0; }

總結

以上是生活随笔為你收集整理的网络分析（带权并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。