当前位置:网站首页>黑点==白点(MST)

黑点==白点(MST)

2022-06-25 06:43:00 mfy的1号小迷弟

黑点==白点(MST)

题意:

给一张无相连通图,每条边可能是黑边或白边,问是否存在一种生成树构成使得树上黑边数量==白边数量

2 ≤ n ≤ 1 e 5 , 1 ≤ m ≤ 1 e 5 2\leq n\leq1e5,1\leq m\leq 1e5 2n1e5,1m1e5
思路:

1.把黑边权值看成1,白边权值看成0,对任意处于最小生成树和最大生成树边权和之间的值,都存在对应的生成树

2.显而易见:将最小生成树其中的一条0边删去,那么最小生成树权值至多+1,从而,对任意处于最小生成树和最大生成树边权和之间的值,都存在对应的生成树。

(这不是套娃吗?所以说显而易见嘛: )

原网站

版权声明
本文为[mfy的1号小迷弟]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_45722843/article/details/118767112