最大收益问题
问题分析
经过分析,又根据最大流最小割定理,最大流的流值等于最小割容量。即:实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、
算法设计
构建网络。根据输入的数据,添...
配对方案问题
问题分析
先了解几个概念。
二分图:又称二部图。设G=(V,E)是一个无向图,如果结点集V客分割为两个互不相交的子集(V1,V2),并且图中的每条边(i,j)所关联的两个结点i和j分别属于这两个不同的结点...
优化扩展——重贴标签算法ISAP
首先对所有的结点标记到汇点的最短距离,称之为高度。标高从汇点开始,用BFS方式,汇点的邻接点高度为1,继续访问的结点高度是2,一直到源点结束。
贴好标签之后,就可以从源点开始,...
最大网络流——最短增广路算法
问题描述
设有向带权图G=(V,E),V={s,v1,v2,v3,...,t}。在G中有两个特殊的结点s和t。s称为源点,t为汇点。图中各边的方向表示允许的流向,边上的权值表示该边允许通过的最大可能流量c...