嘉兴做网站的公司,天津定制网站建设公司,广州网站建设市场,wordpress pagesize网络分析
题意#xff1a;
有n个节点#xff0c;一开始彼此独立#xff0c;有两个操作#xff0c;第一个操作时是连接两个节点#xff0c;第二个操作是对一个节点x#xff0c;#xff08;在进行第二个操作时#xff0c;与该点相连的点也会x#xff09; 问每个节点的…网络分析
题意
有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;
}
