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

给个只用跑两次Kruskal的算法

Posted by Heart_Blue at 2016-10-09 16:12:38 on Problem 1679 and last updated at 2016-10-09 16:15:48
简单的思路

跑第一遍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