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

求解sort和stable_sort的区别?

Posted by lkjslkjdlk at 2012-08-11 20:28:29 on Problem 1679 and last updated at 2012-08-11 20:58:42
在kruskal中
sort, wa
stable_sort, ac
在ural和poj都是这样...
求神牛解答

我用的方法是:
先求出mst,然后枚举不在mst上的边.
每次枚举的操作:
设该次枚举到的边为e, 起点为u, 终点为v.将e加入到mst中,则会形成一个环,然后再删去这个环上除e以外最长的一条边,这样得到的还是一颗生成树,设操作完的生成树的权值为wi
那么次小生成树的权值 w = min(wi) 0 <= i < m

每次求环上最长边的方法是先预处理出顶点两两之间路径上的最长边.
预处理的方法是 修改kruskal,每次合并两个森林的时候,一个森林中的每个顶点到另一个森林的每个顶点的最长边肯定是当前合并对应的边,这样kruskal一遍下来可以求出 顶点两两之间路径上的最长边.
这样每次枚举时查询时就是O(1)了.


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