2018.9.1 补充材料
我们队比赛的源代码已于一年前整理至GitHub (C++)，用整数规划求赛题最优解的源代码放在这里 (Python+Gurobi), 只是自己懒，所以一直没在这里更新:P，特此说明。
2017.5.16 初次编辑，最后修改于2017.5.16
昨天总决赛结束了，历时72天的CodeCraft2017终于画上句号。趁着记忆还比较清晰，来更新一下回答。
写在前面：由于本问题限于对赛题的评价，对一些代码层面的细节处理（诸如读图、结果的输出等等）这里不再多花笔墨，以及，比赛体验什么的也不多展开了，相信浏览这个页面的同学们也大多是参加了今年比赛的参赛选手，个中体会，冷暖自知。本人尽量对赛题做出简洁、客观的评价，并简要描述自己队的算法思想。但由于作为本次比赛的参赛选手，难免掺杂主观认知，所谓“不识庐山真面目，只缘身在此山中”，所以如果有表达不妥的地方，还请各位读者海涵，并多阅读其他答案或者与其他选手交流，以期获取更全面的认识。
下面，在对初赛、复赛和决赛赛题给出简评的同时，会重点讨论一下初赛赛题的解法，以供参考。
初赛的赛题描述很简单：给你一个流网络（边有容量和单位流量费用），已知有一些节点有流量需求（消费节点），现要选一些节点部署服务器（服务节点），给消费节点传输流量，使得在满足所有消费节点流量需求的条件下，最小化成本（服务器购买成本+线路流量费用）。
其他条件和要求：
数据规模：
时间和内存限制
简评：非常好的一个NP-hard问题，数据规模和时限的设置比较合理，没有现成的模型可以立即套用，题目本身虽难，但也并不意味着无从入手，有较好的区分度。
关于求解，一个自然而然的方向是：选出一个点集，评价这个点集。不断进行这样的枚举，最后用评价最好的点集构造输出。（另一个方向是整数规划，鉴于整数规划理论难，代码实现更难，这里不予讨论，后面本人整理好相关文档后，将开源用Gurobi求解本次赛题初赛和复赛的代码。）
如何选：方法很多很多，可以枚举（顺序or随机），也可以启发式，这往往是搜索的核心算法所在。
如何评价：最小费用流（min cost max flow）。ps: 最小费用流可以认为是求解算法的底层基础设施，费用流越快，基本上可以搜索的空间就越大，可以实施的操作也越多，得到更优解的可能性也越大。甚至于，说费用流的速度决定了算法能力的上限都一点不为过。从初赛到决赛，我们对费用流的升级路线是：SPFA增广路算法--->原始—对偶算法（"zkw"算法）--->Cost Scaling--->增量式zkw算法--->网络单纯形。网络单纯形的性能是我们实测效果最好的，在官方提供的练习用例上，90s内600节点的图可以跑4w~5w次费用流，800节点的图可以跑1w次费用流。ps. 后来知道增量式方法也可以用在加速网络单纯形上，使得在800节点图上的表现90s内达到跑4w~7w次。
顺着这个思路往下走，就自然地能想到遗传算法、粒子群等寻优算法——初始随机生成一定数量的解（比如，用0-1数组表示一个服务点集，0表示该点不部署服务器，1表示部署），然后迭代若干轮，每一轮用最小费用流做评价，并用交叉、变异等算子推动种群的进化。
这些都是很不错的想法，但是实施起来就能逐渐感觉到难度，最大的困难大概在于评估的速度。随着图规模的变大，费用流的速度会降低，而要得到更优的解，又必须扩大种群规模和进化代数等参数，不解决这个矛盾，算法很快就会到达瓶颈，甚至90s的时间都来不及收敛。这个问题主要存在于使用了遗传算法和粒子群算法的队伍中，使用这两个算法，也许可以帮助一些队伍进入赛区32强，但要靠它们进入4强，非常之难。究其原因，在于：比赛是有限时的，而且限时比较紧，比赛的性质决定了它要选拔的是搜索速度和寻优能力都强的优化算法，遗传和粒子群等群体进化算法的优点是全局优化能力强，但是缺点也是显而易见的，比如速度慢、参数多等（当然有队伍尝试用近似方法加速评估，比如预处理计算好一些启发信息，或者用最大流替代费用流，亦或近似计算费用流等等，但是效果如何就不得而知了），如果给很长的时间去计算，也许它们就是最佳的选择了。
很多采用了局部搜索（Local Search）的队都获得了相当不错的优化结果，我们队也是如此。Local Search是一种古老的优化方法，但是不意味着古老的方法不比“现代”的方法差。注意请不要在意这些名字，因为实施起来，即便是同一种思维框架，具体细节处理上的不同也会使得结果可能有天壤之别。局部搜索的思维框架简单描述就是（模拟退火可以认为属于这个框架）：从一个初始可行解出发，不断改进当前解，如果到了局部最优，尝试用一些策略跳出它，再去改进，如此循环。优点是由于每次操作大多是专注于改进一个可行解，所以速度比较快，缺点就是容易陷入局部最优，需要用一些有效的方式跳出。
下面这个简单无比的算法做一遍，基本就可以稳进区域64强了：对所有消费节点按需求从小到大排序，接下来直接在消费节点上放服务器，从需求最大的开始放，当可行的时候终止；再从需求最小的节点开始减一轮服务器，只要减完可行，并且总成本能降低，就减；最后再从需求最大的增一轮。核心代码不超过100行。
如果再加上一些复杂的局部搜索技术，比如交换（Exchange），则往往能够实现优化效果的飞跃。在本问题中，加上服务器的交换策略，与邻居以及当前可行解的路由上的点进行启发式交换，可以进一步从质上提高解的质量，而且速度是遗传和粒子群所远不能比。
复赛赛题的描述：在初赛赛题的基础上，加入了服务器的差异化约束条件——服务器有10个档次，每个档次的服务器购买成本和容量都不同，每个网络节点的部署费用也可能不同。也就是说，在一个网络节点部署一台服务器的成本 = 该服务器的购买成本 + 网络节点的部署成本。
数据规模：
时间和内存限制：
简评：非常不错的问题升级，难度进一步加大的同时，实现了从初赛赛题较为平稳的过渡，选手可以基于初赛对赛题的理解修改自己的算法。
注：比赛官网上对复赛数据规模的描述十分不合理，基本不包含什么信息量，可以认为是干扰信息，如果真出现了上限的最大规模，在时限和内存不变的条件下，几乎是不能做的。数据规模的确认在复赛前期耽误了不少选手的时间，不过好在复赛真实比赛中用的数据规模比较合理（最大是800节点, 5000+条边）。
之所以说是“NP-hard”的双层叠加，是因为除了要选择比较好的部署服务器的点集之外，还要确定服务器的档次，而一台服务器可选的档次就有10个之多，因而相当于面对两个NP-hard问题。比如，若选择30个节点部署服务器，加入档次的条件后，即便确定了部署的服务器数量、在哪部署，还有10^30种可能。换句话说，即便告诉你最优解中在哪些节点上部署了服务器，也很难找到最优解。问题的难度可想而知。
关于解法，初赛的基本思想可以继续沿用，但是要考虑服务器档次这个重要的条件。大体来说，选位置的优先级还是高于降档。有一个降档的基本做法是必须的：每次计算完费用流后，根据服务节点的输出流量确定相应的档次，可以有效避免成本的浪费。在搜索算法的前期，我们基本不考虑服务器档次，执行可行解中服务器的减少、增加和交换等操作的组合，和初赛算法类似；后期将档次的调整引入这些操作算子，并在算法的最后把降档和升档作为两个相对独立的操作过程又执行了一遍（即便看起来有如此多的操作，最后的用时都没有超过80s）。我们这样的做法十分有效，比如，复赛官方提供的最后一批练习用例，高级用例case0可以解出388600以内，中级用例也大多可以解出质量相当好的近似解（与最优解的距离在500以内）。
决赛赛题的条件比较多，可以访问这个页面获得题目描述: 赛题介绍 | HUAWEI软件精英挑战赛
简而言之，是在复赛的条件基础上，除了进一步增加数据规模，问题的性质也由优化问题变为博弈问题。博弈体现在两支队伍每一轮对消费节点的争抢上。
简评：将组合优化与博弈结合，命题思路极具创意。但是赛题的延续性被强烈地破坏。
以下为个人观点。命题的思路非常好，甚至不少被初赛复赛弄得精疲力竭的队伍看到决赛赛题后又燃起了做题的斗志。但是从做题的体验来看，本人认为，决赛的命题是失败的。主要有以下几个原因：
关于决赛赛题的解法，不再多说，我们的体会是除了费用流之外，初赛复赛的深入和努力基本都用不上，另外，个人也不认为存在什么通用的算法可以做好决赛的问题。
关于赛题的评价，到这里也就差不多了，如果读者有什么问题，在评论区提出，或者私信皆可。本回答还将根据自己的认知和他人的建议作出合适的修改。
以上。
2017.3.11初次编辑，最后修改于2017.3.17
谢邀。看了一下赛题，是一道很难的NP-hard问题。
去掉各种背景描述，这个问题就是流网络中的设施选址问题。经典的设施选址问题（Facility Location）是没有“网络”的概念的（如果有，可以视为一个二分图），是NP难，不过有无数的论文给出了各种求解方法；经典的最小费用流则可以多项式时间求解；这个问题相当于两个问题的组合，所以要么用整数规划，要么用其他启发式算法吧。
整个问题的模型其实很简单，困难在于：一、 不能用任何第三方ILP solver，只能用C/C++/Java自己实现算法（在我看来，理解原理是一回事，用高效的数据结构实现又是一回事。比如，多少人能手动把修正单纯形、割平面等算法撸出来）；二、限时90s，对于一个NP-hard的问题而言，是很紧了，这就要求所设计的算法不能用大量的时间做低效的搜索；三、就是允许用ILP solver，也不一定能在90s内解出大规模图。
ps. 据说华为内部研究团队是用整数规划做的。
