最大收益问题

问题分析

经过分析,又根据最大流最小割定理,最大流的流值等于最小割容量。即:实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、

算法设计

  1. 构建网络。根据输入的数据,添加源点和汇点,从源点s到每个实验项目Ei有一条有向边,容量是项目产生的收益pi。从每个实验仪器Ij到汇点t有一条有向边,容量是仪器费用cj,每个实验项目到该实验项目用到的仪器有一条有向边容量是
    ∞,创建混合网络。
  2. 基于ISAP算法求网络最大流。
  3. 输出最大收益及实验方案。最大收益实验方案就是最小割中的S集合去掉源点。在最大流对应的混合网络中,从选点开始,沿着cap>flow的边深度优先遍历,遍历到的结点就是S集合,即对应的实验项目和仪器就是选中的实验方案。

代码实现

  1. 输出最大收益方案

  1. 构建混合网络

算法复杂度

时间复杂度:找到一条可增广路时间为O(V),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

方格取数问题

问题简介

从一个矩阵中选取一些数,要求满足任意两个数不相邻,使这些数的和最大。实际上就是讲矩阵中的数分为两部分,对矩阵中的点进行黑白着色。

问题分析

黑色方格作为一个集合X,白色方格作为一个集合Y,可以将一个图分为两部分,构成一个二分图。添加源点和汇点,从源点向黑色方格连一条边,容量为该黑色方格的权值,从白色方格向汇点连一条边,容量为该白色方格的权值,对于每一对相邻的黑白方格,从黑方格向白方格连一条边,容量为无穷大。

同样是求出最小割,选中方格的最大权值=所有方格权值之和-最小割容量。

算法设计

  1. 构建网络
  2. 求网络最大流。
  3. 输出选中物品的最大价值、物品选择方案。

选中物品的最大价值=所有物品价值之和-最大流值
注意:切割线切到的边容量是没选中的方格权值。

方格取数1

物品选择方案就是最小割中的S集合中的黑色方格和T集合中的白色方格。找到最小割后,从源点出发,沿着cap>flow的边DFS,遍历到的结点就是S集合,没有遍历到的结点就是T集合。输出S集合中的黑色方格和T集合中的白色方格。如上图所示。

算法详解

假设整个图如下图所示。

方格取数1

  1. 构建网络,根据输入的数据,绘制二分图,添加源点s和汇点t,从黑方格向白方格连一条边,容量为∞,创建网络。

方格取数3

  1. 在混合网络上用ISAP算法求网络最大流,找到如下6条增广路径。
    • 增广路径:10-6-9-0.增流5。
    • 增广路径:10-8-9-0.增流15。
    • 增广路径:10-4-7-0.增流34。
    • 增广路径:10-2-5-0.增流70。
    • 增广路径:10-2-3-0.增流21。
    • 增广路径:10-2-1-0.增流75。

方格取数4

切割线中被选中的就是红色圈圈的结点,选择的道路是从源点出发,按照cap>flow的结点(这里面只有7和9两个结点)去深度遍历,这就是S集合;1、3、5和2是T集合。
所以选中的黑点为7、9,白色为2。

代码实现

(1)构建网络

(2)输出挑选物品的最大价值

(3)输出选中的物品编号。

算法复杂度

时间复杂度:找到一条可增广路时间为O(V),最多会执行O(VE)次,因为关键边的总数为O(VE),因此总的时间复杂度为O(V2E),其中V为结点个数,E为边的数量。

空间复杂度O(V)。

旅游路线问题

问题分析

给定一张地图,图中结点代表景点,边代表景点可以直达。现要求找到满足下面要求且途径景点最多的一条旅游线路:

  1. 从最东端起点出发,从东往西经过若干个景点到达最西端的景点,然后再从西向东回到家(可途径若干景点);
  2. 除起点外,任何景点只能访问1次。

算法设计

  1. 构建网络。根据输入的数据,按顺序对景点进行编号,即景点i对应结点i,对每个结点拆点,拆为两个结点i和i',且从i到i'连接一条边,边容量为1,单位流量费用为0;源点和终点拆点时,边的容量为2,单位流量费用为0;如果景点i到景点j可以直达,则从结点i'到结点j连接一条边,边的容量为1,单位流量费用为-1,创建混合网络。
  2. 求网络最小费用最大流。
  3. 求出最优的旅游线路。从源点出发,沿着flow>0且cost≤0的方向深度优先遍历,到达终点后,再沿着flow<0且cost≥0的方向深度优先遍历,返回源点。

代码实现

  1. 构建网络

  1. 求网络最小费用最大流

  1. 输出最优的旅游路线