【TJOI2015】线性代数

Problem

TJOI2015
bzoj3996

Analysis

请先思考后再展开

把题意转化为点有点权,边有边权,求权值和最大的点导出子图
然后想了想普通的网络流,感觉无法解决,然后就不会了
其实是个最小割……好久没用了就完全没想到
其实有经验的话,这种决策类的东西,不能贪心基本都是网络流了吧

最大化答案,即最大化总边权+点权-被舍去的部分
如果一条边的两个点都没有被舍去,那么边权就必须舍去
基于这个思路构图就好了

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/1b03.html
转载请注明出处,谢谢!