初赛
题目
很好，网上找了一会也没有找到题目，我只想说，华为你把往年的题的链接给一下可好？
凭借记忆，初赛的题目大概是，有一个网络，要在上面部署cdn服务器，怎么部署既能满足用户需求， 又能使得部署费用最少。
具体一点，相当于一个无向图，有一些点是小区，每个小区都有视频业务的需求，而且需求量不一样，每条边是一条链路， 链路有它的带宽限制。现在需要部署cdn服务器，让每一个小区的视频业务都能满足，同时部署cdn服务器的费用越低越好。
每一个点都可以部署cdn服务器（包括是小区的点），每一个小区有一个需求值，每一条边是一条链路，每条链路都是双向的， 每条链路有一个链路容量和一个单位费用（使用链路上一个单位的流量需要多少钱）。cdn服务器数量无限，cdn服务器输出能力无限， 同样cdn服务器也有一个单价。
限制：不能使用第三方库，程序运行时间不超过60s。
简单分析
这个需要一步一步来分析：
- 该选择哪些点来部署服务器？
- 在部署好了服务器的情况下，流量该如何流，才能满足所有用户，并且使得费用最小？
这就是这个题目的两个核心问题。
该选择哪些点来部署服务器？
这是这个题目最难的一部分，因为这个选择是一个NP难的问题，所以是没有现成的解法来教你如何求解这个问题的， 通常都是将它变成一个整数规划模型，然后使用求解器来求解。但是由于不能使用第三方库，所以代码全靠手写， 那么这个问题基本上只能使用启发式算法来解。
那么有哪些常用的启发式算法呢？遗传算法、模拟退火、蚁群算法、粒子群算法等。
很好，那么从哪个算法开始呢？显然都不用，第一步当然是写一个最简单的版本，先熟悉问题，在深入问题。
最简单的版本（原始想法）：
版本1：初始每一个小区都给一个cdn，然后再尝试一个个cdn删除，直到不能降低费用，或者不能满足用户需求为止。
版本2：初始没有cdn，然后尝试一个小区一个小区添加cdn，直到需求满足且不能降低费用为止。
初始版本的想法非常简单，但是很遗憾，这个想法在初赛的简单用例上能直接跑出最优解…
(有时候问题就是这么简单，只不过很多人还没开始就觉得难，然后就没有然后了)
在部署好了服务器的情况下，流量该如何流，才能满足所有用户，并且使得费用最小？
解决这个问题很简单，使用最小费用最大流就解决了。
使用最简单的增广路写法就好。
进阶分析
同样的，两个步骤的想法。
该选择哪些点来部署服务器？
由于最初始的版本效果很好，那么在这个基础上还能加强吗？
当然能，很简单就能想到几个操作方法：
- cdn移动。现在cdn都是直接放在小区上面的，所以自然可以尝试移动cdn，只移动一步， 如果移动能降低费用就移动，否则维持原状。
- cdn删除。这个删除不同于上面的原始想法中的删除，这个删除是根据cdn移动来的，如果有cdn移动成功了， 那么意味着图的结构变了，有的点就也许就可以删除了。
很遗憾，初赛使用的就是这个思路做的，最后大概成渝前3的水平…
在部署好了服务器的情况下，流量该如何流，才能满足所有用户，并且使得费用最小？
上面选择了增广路写法。
但是，注意到时间限制60s，在这种分两步走的策略里面，需要跑很多次费用流， 这时候的问题就是如何解决好这个问题，也就是用时尽量少。
最小费用最大流：
这里我首先使用的是增广路解法，使用SPFA计算增广路的最短路径。
由于在一次求解最小费用最大流的过程中，需要反复的调用SPFA，那么在重复进行SPFA的过程中，不用每一次都重头开始， 也就是一部分最短路径的结果可以保留，这样在下一次计算时就可以少很多的计算量。
使用这样的方法，跑高级用例也没有问题，否则高级用例会有压力。
由于上面部署的思路太简单了，这个最小费用最大流的魔改是我觉得自己最有意思的地方了。
（具体用时忘记了…太过久远）
代码
参见github2017-codecraft
在一年之后，看自己一年之前写的代码，真的写得稀烂…估计再过一年又会嫌弃现在。
复赛
题目
和上面的题目其实一样，
// TODO