解题思路:在两个集合合并时将每个节点的当前大小保存,将时间复杂度从(nm)压到了(n2)
注意事项:注意使用启发式合并,不然还是会超时
参考代码:
#include<bits/stdc++.h> using namespace std; long long ans[10005]; long long add[10005]; int f[10005]; int siz[10005]; int n,m; int find(int x) { if(f[x]!=x) { return f[x]=find(f[x]); } return x; } void marey(int x,int y) { int a,b; a=find(x); b=find(y); if(a!=b) { for(int i=1;i<=n;i++) { ans[i]+=add[find(i)]; } for(int i=1;i<=n;i++) { add[i]=0; } if(siz[a]>siz[b]) { swap(a,b); } f[a]=b; siz[b]+=siz[a]; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { f[i]=i; siz[i]=1; } while(m--) { int t,a,b; scanf("%d%d%d",&t,&a,&b); if(t==1) { marey(a,b); } else { add[find(a)]+=b; } } for(int i=1;i<=n;i++) { printf("%d ",ans[i]+add[find(i)]); } return 0; }
0.0分
1 人评分
模拟计算器 (C语言代码)浏览:892 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1049 |
C语言程序设计教程(第三版)课后习题1.5 (C++代码)浏览:1095 |
淘淘的名单 (C语言代码)浏览:1104 |
wu-淘淘的名单 (C++代码)浏览:1339 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:745 |
蛇行矩阵 (C语言代码)浏览:536 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:561 |
DNA (C语言代码)浏览:750 |
核桃的数量 (C语言代码)浏览:872 |