| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:emmmmm终于A了,分享一个关于kruskal的优化,带权并查集,直接TLE到282ms。。。In Reply To:emmmmm终于A了,分享一个关于kruskal的优化,带权并查集,直接TLE到282ms。。。 Posted by:kongzyu at 2019-01-26 17:06:36 > RT
> w[i]初始值为1
> int find(int x){
> int temp=f[x];
> if(f[x]==x) return x;
> f[x]=find(f[x]);
> w[temp]+=w[x];
> w[x]=0;
> return f[x];
> }
> w[i]记录子叶,每次判断加入的边,有w[i]==n就直接跳出,不用跑完所有的m条边。。。
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator