BZOJ 2466 [中山市选 2009] 树

发布于 2017-07-06  121 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2466

题意:树上开关灯问题,按了一个点改变它和与它相邻的所有点的状态,最初均为关,问至少多少下全开


直接高斯消元喽... 注意可能存在按不按都可以的自由元,那么消元的时候先不按跳过。贪心的不按所有自由元不一定是最优解,可以暴搜每个自由元按还是不按更新答案...

话说能证明自由元最多个数吗 qwq,复杂度怎么回事呢 qwq

 

 


一个非常弱的准退役OIER