标签为 [最小割] 的文章

POJ2987 Firing

题目大意 你要对一些员工进行裁员,裁掉一个员工都可以获得一些收益(可能为负)。员工之间有上下级关系,要裁掉一个员工,必须要裁掉他的所有下属。问获得的最大收益是多少。 Solution 对于这种最大收益的题,我们可以考虑构造最小割模型。假设我们已经裁掉了那些收益为正的人,但不能裁了上司而不裁下属。设置超级源,将它与所以收益为正的点连边,流量为w[i],表示裁掉了这个人,并将初始答案加上w[i],若割掉这条边,就表示不拿这个人的收益了。再将所有收益为负的点向一个超级汇连边,表示不裁这个人,流量为-w[i],若割掉这 ......