| ||||||||||
| 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