华为精英挑战赛初赛题

• 运行环境： eclipse for java
• 启动方法： 必须输入两个命令行参数：用例数据文件 结果输出文件 ，然后从Main.java 启动程序。

 例如我们的根目录下就有一个用例数据文件case0.txst和输出文件result.txt,所以命令行参数为：case0.txt result.txt

 首先对题目进行简单处理，以方便建模

 1. 将所有的消费结点都合并为一个汇点t，相当于把每个消费结点对应的边的终点合并在一起，每一条边的带宽等于对应消费结点的需求。
 2. 增加一个网络结点s，与每一个放置服务器的网络结点都相连接（后边说明哪些会放置），边的方向指向网络结点，带宽无限大，费用为0。
 3. 网络链路上的上下行流量互不干扰，所有每一条网络链路处理量为双向边，容量和费用都与链路上提供的相等。

•  通过遗传算法来启发式搜索哪些网络节点放置服务器；
•  然后求解最大流:使用ford_folkerson算法；
  使用ford_folkerson算法的基本思路是：利用dijkstra算法查找原点到汇点的最短路径，遍历最短路径把路径上最小的剩余带宽（边残存容量）作为这个路径的残存容量P，然后更新残存网络（把残留路径上的每天边的残存容量都减P），从复这个过程直至没有增广路径为止（由于边的容量限制，没有原点到汇点的路径）。
   最大流求解过程中每一条最短路径就是流路径，每条最短路径上的费用和就是消费节点的某一条宽带路径的费用，通过某一个消费结点的所有路径费用之和就是该消费节点的总费用。
•  因为汇点相连接边的容量等于消费结点的需求，所以最大流的上界就是等于需求之和。只有当最大流恰好等于他上界，也就是等于所有消费节点的需求和时，放置服务器的位置才是可以满足消费节点的需求的。  
•  在满足消费需求的前提下，服务器的费用加上消费结点的费用之和 就是总的费用，当总的费用最低时就是最优解。