poj2987专题

poj2987--Firing(最大权闭合图)

poj2987:题目链接 题目大意:有个公司,n个员工,m个关系,因为亏损,所以要辞退一些员工,给出辞退每个员工会给带来的收益(有正有负),关系x y代表x是y的上司,如果辞退一个上司,那么他手下的人都会退出,问最大的收益,和要删除的人数。 因为删掉一个上司,员工也会离开,所以最后求的删除的人会是一个闭合图,也就是求最大权闭合图,将其中正值k的点i连接边<s,i>值为正,原图中的边值为正无穷,