算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1E4 + 11;
int n, m, p[N], sz[N], ans[N], val[N];
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]); /// 启发式合并 可以和 路径压缩一起用?
// while(x ^ p[x]) x = p[x];
// return x;
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return ;
for(int i = 1; i <= n; ++ i) ans[i] += val[find(i)];
if(sz[x] > sz[y]) swap(x,y);
p[x] = y;//链接
sz[y] += sz[x];//启发
memset(val, 0, sizeof(val));
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) p[i] = i, sz[i] = 1;
for(int i = 1; i <= m; ++ i){
int x, y, z; cin >> x >> y >> z;
if(x & 1){
if(y == z) continue;
merge(y,z);
}
else if(x == 2){
val[find(y)] += z;
}
}
for(int i = 1; i <= n; ++ i) cout << ans[i] + val[find(i)] << " ";
return 0;
}
算法2
C++ 代码—优化了n的遍历
y总’
#include <bits/stdc++.h>
using namespace std;
const int N = 1E4 + 11;
int n, m, p[N], sz[N], ans[N], val[N];
vector <int> nod[N];
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]); // 路径压缩
// while(x ^ p[x]) x = p[x];
// return x;
}
void merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return ;
//for(int i = 1; i <= n; ++ i) ans[i] += val[find(i)];
if(sz[x] > sz[y]) swap(x,y);// 小子树链接到大子树
for(const auto &u : nod[x]){
ans[u] += val[x];
ans[u] -= val[y];//这个操作通过每次把从当前点到根节点路径上的各个点权值加和起来-然后再减,维护各个子段的·独立
nod[y].push_back(u);//最后输出时再加上它所属的根节点
}
// for(const auto &u : nod[y]){
// ans[u] += val[y];
// //ans[u] -= val[y];//这个操作最后通过把从当前点到根节点路径上的所有权值加和起来
// //nod[y].push_back(u);
// }
// for(const auto &u : nod[x]){
// //ans[u] += val[x];
// //ans[u] -= val[y];//这个操作最后通过把从当前点到根节点路径上的所有权值加和起来
// nod[y].push_back(u);
// }
p[x] = y;//链接
sz[y] += sz[x];//启发
//memset(val, 0, sizeof(val));
nod[x].clear();//合并后就清除
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++ i) nod[i].push_back(i);//点单独存自己
for(int i = 1; i <= n; ++ i) p[i] = i, sz[i] = 1;
for(int i = 1; i <= m; ++ i){
int x, y, z; cin >> x >> y >> z;
if(x & 1){
if(y == z) continue;
merge(y,z);// y和z合并---利用根节点,加值作差,小接大
}
else if(x == 2){
val[find(y)] += z; //给根节点加上值,代替其子节点都也加上了这值,在合并时加上
}
}
for(int i = 1; i <= n; ++ i) cout << ans[i] + val[find(i)] << " ";
return 0;
}