Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:emmmmm终于A了,分享一个关于kruskal的优化,带权并查集,直接TLE到282ms。。。

Posted by 2251307025 at 2024-12-07 16:30:11 on Problem 1751
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator