标签为 [最小生成树] 的文章

BZOJ2654 tree

在WC划水后的第一篇博客,算是庆祝戊戌年的到来(依然在划水) 题目大意 给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。 题目保证有解。 Solution 最小生成树?kruskal?prim?应该都可以。我使用了方便的kruskal。 然而有一个限制:恰好使用need条白色边。 考虑给让白色边的边权都加上一个正数,这样就可以在最小生成树中选择更少的白色边;加上一个负数同理。于是可以枚举这个值,给所有白色边都加上这个值后跑最小生成树,再看生成树的白色边是不是need条。而这个值显然是可以二 ......