运行环境为：VS2017
有问题欢迎私信
多段图的最小成本问题
实验要求
设G=(V,E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi: 1ik，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，图中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中：uVi，vVi＋1。如图所示。
资源分配问题
实验要求
资源总数为，工程个数为。给每项工程投入的资源不同，所获得的利润也不同。要求把总数为的资源，分配给个工程，以获得最大利润的分配方案。
动态规划是一种有效的算法设计策略，尤其适用于解决具有最优子结构和重叠子问题的问题。在多段图的最小成本问题中，动态规划被用来寻找从源节点s到汇点t的最低成本路径。这个问题通常涉及到一个有向图G，其顶点集V被分为k个不相交的子集Vi，每个子集之间由边相连，且源s位于V1，汇t位于Vk。
算法的核心思想是通过逐步构建最优解，从最后一段开始向前回溯。在每一段中，我们计算当前顶点到汇点的最小花费，以及这条最小花费路径上的前一个顶点。这可以通过一个二维数组cost[i]和path[i]来记录。cost[i]表示顶点i到达汇点的最小花费，而path[i]存储的是使cost[i]达到最小的前一个顶点的编号。
初始化时，所有cost[i]设置为一个非常大的值，path[i]设置为-1，除了cost[n-1]，它被设置为0，因为汇点到自身的成本默认为0。然后，从倒数第二个顶点开始，遍历每个顶点的邻接节点，更新cost[i]和path[i]。当找到一条使得总成本更低的路径时，就更新这两个值。
动态规划的决策过程是一个逐步细化的过程，从最后一段开始，逐步向前推进，直到找到源点s。在每一步，我们都会根据当前的cost[i]和path[i]更新route数组，它记录了从源点到汇点的最短路径上的顶点顺序。当route[i]等于汇点的索引时，算法结束。
在实际编程实现中，可以使用邻接链表来表示图，每个NODE结构体包含邻接顶点的编号、费用和指向下一个邻接顶点的指针。在C++代码中，我们定义了这些数据结构，并提供了fgragh函数来执行动态规划算法，计算最短路径并打印结果。
资源分配问题则是一个与多段图最小成本问题相关的优化问题。目标是在有限的资源下，将资源分配给多个工程，以最大化利润。这通常涉及到建立一个成本-收益矩阵，通过动态规划或其他优化算法寻找最佳分配策略。在资源分配问题中，我们需要考虑每个工程对资源的需求和对应的收益，然后找到一个资源分配方案，使得总收益最大。
动态规划在多段图的最短路径和资源分配问题中都扮演着关键角色，它通过分解问题并逐步构造最优解，有效地解决了这两类优化问题。
