【网络流24题】搭配飞行员(太空飞行计划问题)(最大闭合图)

太空飞行计划问题

题目分析:

   是一道中问题,就不深入的分析了。就是叫你求给你M个实验,N个仪器。每个实验要用到N个仪器中的一些,而每个仪使用每个仪器都要花费一些钱。而完成每个实验会有一定的报酬,现在叫你求出最大的利润。

利润 = 总收益 - 总花费

算法分析:

   最大权闭合子图。

建模分析:

我们可以根据最大闭合子图的算法思想,建立一个图,其实就是裸题。

1、我们建立两个超级点S,T。

2、对每个实验跟S链接一条容量为收入的边。

3、对每个一起跟T链接一条容量为花费的边。

4、对每个实验要用到的一起链接一条容量为无穷大的边。

代码就是dinic,话说也找不到网站去交。

原文地址:https://www.cnblogs.com/fengzhiyuan/p/7922241.html