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 |
emmmmm终于A了,分享一个关于kruskal的优化,带权并查集,直接TLE到282ms。。。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