最大收益问题 问题分析 经过分析，又根据最大流最小割定理，最大流的流值等于最小割容量。即：实验方案净收益=所有实验项目收益-最大流值。所以只需要求出最大流值即可、 算法设计 构建网络。根据输入的数据，添加源点和汇点，从源点s到每个实验项目E…

配对方案问题 问题分析 先了解几个概念。 二分图：又称二部图。设G=(V,E)是一个无向图，如果结点集V客分割为两个互不相交的子集（V1,V2），并且图中的每条边（i,j）所关联的两个结点i和j分别属于这两个不同的结点集（i∈V1，j∈V2…

优化扩展——重贴标签算法ISAP 首先对所有的结点标记到汇点的最短距离，称之为高度。标高从汇点开始，用BFS方式，汇点的邻接点高度为1，继续访问的结点高度是2，一直到源点结束。 贴好标签之后，就可以从源点开始，沿着高度h(u)=h(v)+1…

题目4 和为S的两个数字 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 题目解析 我们知道，两个数字，距离越远，乘积越小，距离越近乘积越大。所以我…

题目1 二叉树的深度 题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 题目解析 如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么…

线性规划问题 遇到一个线性规划问题，该如何解决呢？ 1. 确定决策变量。 2. 确定目标函数。 3. 找出约束条件。 4. 求最优解。 一般线性规划问题可以表示为如下形式。 约束条件为： 变量满足约束条件的一组值成为线性规划问题的一个可行解…

最大网络流——最短增广路算法 问题描述 设有向带权图G=(V,E)，V={s,v1,v2,v3,…,t}。在G中有两个特殊的结点s和t。s称为源点，t为汇点。图中各边的方向表示允许的流向，边上的权值表示该边允许通过的最大可能流量…