在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)了.

• Re:求解sort和stable_sort的区别? (40) 416221843 2017-07-09 13:15:41
  • Re:求解sort和stable_sort的区别? (203) 416221843 2017-07-09 13:24:40