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:给个只用跑两次Kruskal的算法

Posted by Gitfan at 2017-02-25 20:44:22 on Problem 1679
In Reply To:给个只用跑两次Kruskal的算法 Posted by:Heart_Blue at 2016-10-09 16:12:38
> 简单的思路
> 
> 跑第一遍Kruskal的时候,给生成树的边都打上标记。
> 
> 然后在跑第二遍的时候,在同等权值的条件下,让打了标记的排在后面(重新sort一遍即可)。
> 
> 这样如果把没有打标记的边放入生成树的话,就说明生成树不唯一
> 
> class Edge
> {
> int weight;
> int flag;
> int u;
> int v;
> }
> 
> bool cmp(Edge &e1, Edge &e2)
> {
>     if(e1.weight != e2.weight) return e1.weight < e2.weight;
>     return e1.flag < e2.flag;
> }

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