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