ZOJ 2071 最大权闭合图

题意:

有m个订单,每个订单都能获取一定的收益,但是完成每个订单都需要购买不同的机器,求最多能挣多少钱,需要完成哪些订单,购买哪些机器。

题解:

最大权闭合图建图,S连所有的订单,边容量为利润,订单连所有的机器,边容量为INF,机器连T,边容量为成本。

关键是求方案。

我想的是dfs图找割边。。和网上的做法效果上应该是一样的。。网上大多都是分两次bfs找的~

代码请参考:http://blog.sina.com.cn/s/blog_68629c770100z2v9.html

写了一天网络流,实在不想写了。。。偷懒了~

没有人能阻止我前进的步伐,除了我自己!
原文地址:https://www.cnblogs.com/proverbs/p/2850328.html