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

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

Posted by kongzyu at 2019-01-26 17:06:36 on Problem 1751
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