Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:给个只用跑两次Kruskal的算法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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator