华为2017软件精英挑战赛赛题:cdn内容分发网络中,中心服务器部署,使得部署成本与到消费者的传输成本之和最小。
branch表示版本提交的日期。
4.05最终采取的方案:
1.最大流最小费用问题,采取spfa算法,注意最后要深搜去正向反向重复传流量的边。
2.服务器部署采取先增后减的策略:
 (1)从需求量最大的一个消费者的代理节点开始部署第一个服务器,对spfa算法做改进。
 后续不断增加服务器,并优先满足需求量较多的消费者。
 直到所有的消费者需求都被满足。
 
 (2)对(1)中得到的服务器列表,进行删减。
 删减标准是:若减去某一个服务器,总费用减少,则删除。
 
3.对增减服务器设置一个阈值,
 增加时,若到某个消费者节点的传输成本大于某一值,增加一个服务器;
 减少时,若服务器的传输流量成本小于某一个值,减少一个服务器。