bzoj 2753: [SCOI2012]滑雪与时间胶囊 kruskal

看复杂度就不是最小树形图。显然是MST魔改以下。这个图相当于很大一部分是有向边,有一些小部分是无向边。按照从上(1号点高度)向下的顺序来,自然也就保证了正确性,保证了每次是从1号点的联通快连出去,用MST处理就行了,

以下为正解;

第一个问宽搜解决。

第二个问,按照第一关键字有向边指向点高度降序,第二关键字边权升序排序,然后做正常的MST即可。

注意一条边如果其两侧有任意一个点是不可能到达的,那么这条边就忽略,因为这个WA了几次。

发表评论