最佳派对问题的解题报告

大榕树 \ 信息学奥赛 \ 解题报告

最佳派对问题的解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=150

【正文】

〖思路〗

　　本题是经典的求二部图最大匹配，使用标号法解决。

〖算法〗

　　求二部图最大匹配的算法。

　　附加网D的构造

　　1．将每个中国同学变为一个点Xi（i=1..n），每个外国同学变为点Yi（i=1..n），新增原点s与汇点t。

　　2．由s向每个点Xi发出一条边，容量为1。

　　3．若中国同学i与外国同学j可以形成搭配，则新增一条有向边（Xi，Yj），容量为1。

　　4．由每个点Yi向t发出一条变，容量为1。

　　标号法

　　1．清零流：将每条边的流量都清为0。

　　2．寻找可改进路

　　　　(1) 将源点s标号为1，其余顶点标号为0。

　　　　(2) 检查所有标号为1的顶点A：对于所有边（A，B）（称为前向弧），若B标号为0，且该边未满，则将B标号成为2；对所有边（B，A）（称为后向弧），若B标号为0且该边上有流，也将B标号为2。所有从A得到标号的点的前趋记为A。最后将A标号成2。

　　　　(3) 重复第(2)步，直到t获得标号（找到可改进路）或再无标号为1的点（无法找到可改进路）为止。

　　如果找到了可改进路，进入步骤3；否则最大流已经找到，退出标号法。

　　3．增加流

　　从t起，沿着记下来的前趋节点得到一条路经S：s→V1→V2→V3→V4→…→t。对于S上的每条边（Vi，Vj），若该边为前向弧，则将该边流增加1（对于本题来说），否则将该边的流减少1。这样就可以得到一个新的增加了流的网络。

　　回到步骤2。

　　得到答案

　　1．最大流 |V| 即为最佳派对数。

　　2．若边（Xi，Yj）上有流，则中国学生i与外国学生j配对。

〖数据结构〗

　　使用临接表。

作者：林元
来源：福州一中
时间：2001-07-31

上一篇：皇宫看守问题的解题报告
下一篇：《无线电测向》解题报告