Beyond the Void

经过几天努力终于做完了线性规划与网络流24题，同时对网络流和二分图的理解也上升到了一个新的高度。把所有题解发上来供大家参考，还请多多指教。

感谢ShingRay发现本文一个错误，现已修正。

BYVoid原创 线性规划与网络流24题_解题报告Ver 2 (48KB)

另外附上 线性规划与网络流24题 (1.90MB) 感谢王晓东老师给我们提供这么多好题。

几点说明

1. 本题解提供所有问题的解析和大部分问题的C++程序源代码，以及个别数据的勘误。
2. 本题解只讨论问题的分析和建模，具体的实现参照代码。代码中所有网络最大流算法均用Dinic实现。
3. 读者应具备图论、最短路径、网络流的基础知识，并掌握至少一种网络最大流和最小费用最大流的算法。
4. 建议读者在阅读题解前先进行充分的思考，确认无法独立解决后再看题解。
5. 问题8 机器人路径规划问题 是个经典难题，暂时还未解决，欢迎大家讨论。
6. 本题解系个人原创，请勿商业转载，非商业转载请注明来源。

问题一览

把每个用户和每个站点都看成一个顶点。建立网络，从源点S向每个用户连接一条容量为收益的有向边，每个用户向相关的两个站点连接一条容量为无穷大的 有向边，每个站点向汇点T连接一条容量为成本的有向边。求出网络最小割集的容量就是Maxflow=（未被选的用户的收益之和 + 被选择的站点的成本之和）。设Total为所有用户的收益之和，我们要求的是（被选的用户的收益之和 – 被选择的站点的成本之和），恰好等于Total – Maxflow，就是最大收益。

为什么是这样的？因为任何一个可行割集对应了一个满足条件的方案，具体来说被选择的顶点就是S集合中的顶点，而割集对应了cut=（未被 选的用户的收益之和 + 被选择的站点的成本之和），我们为了要求的（被选的用户的收益之和 – 被选择的站点的成本之和）= Total – cut尽量大，Total一定，所以要让cut尽量小，直至最小割集。

Dinic秒掉。

Read the rest of this entry »

这是一个网络最大流问题。读题发现有很明显的模型，入口和出口的通道容量都是1，内部通道没有容量限制，求从1到N最多通过的人数。

源为1，汇为N，把连接源和汇的通道建立为容量为1的边，其余的边容量为无限，求从源到汇的网络最大流就是结果。

题中所给N<=200，可以用一般的最大流算法解决。我的程序是Dinic。

Read the rest of this entry »

Read the rest of this entry »