对于我们题目1-M相当于确定的服務器组合,M+1 - M+N+1是消费节点S和T是虚拟的超级源点和汇点
链路的权重就是图中的cost(即单位费用),这个替换了SPFA求最短路径的算法(即最短路径茬该图就等于最小单位费用)
各个消费节点的需求转化为T的需求也即要求的最大流量(各个消费节点需求相加)
①确定当前服务器组合1-M。
②利用SPFA算法求得到T的最小单位费用然后用深度搜索找到该条路径,取路径边能容纳的最小流量流过更新边和T的需求,并计算此条链蕗费用(我们之前是求得大部分路,然后用最小单位费用排序而这个步骤先用SPFA确定了最小单位费用,然后去找路线个人感觉这部分省嘚时间较多。)
③循环②的步骤直到T的需求全部满足或者所有可能路径全部搜完结束,求出此次服务器组合的最小费用(搜索终止条件可以优化,不然搜索的太多)