网络流与二分图.ppt

网络流与二分图问题 主要涉及内容 网络流：网络最大流、最小费用最大流 二分图：二分图最大匹配，最大独立集，最小路径覆盖 在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。 农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。 根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形 交点1是水潭，交点M是小溪 一个简单的例子-网络的最大流问题 网络与流 求最大流的上些算法 基于增广路的算法（Ford-Fulkerson方法） Edmonds-Karp算法（最短增广路算法） SAP(改进的最短增广路算法) 基于预流推进的算法（Preflow push方法） Push-relabel（压入重标记算法） Relabel-to-front（重标记与前移算法） 基于分层思想的网络流算法 Ford-Fulkerson Demo Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method Ford-Fulkerson Method 基于Ford-Fulkerson的Edmonds-Karp 改进的最短增广路算法（SAP） 如何提高算法效率：通过降低每次寻找增广路的时间复杂度 最短增广路：每次寻找包含弧的个数最少的增广路进行增广 如何寻找最短增广路？ 使用距离标号的方法 所谓距离标号，就是某个点到汇点的最少的弧的数量（另外一种距离标号是从源点到该点的最少的弧的数量，本质上没什么区别）。设点i的标号为D[i]，那么如果将满足D[i]=D[j]+1的弧(i,j)叫做允许弧，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果 但是最短增广路不一定都对应的一条允许路，所以有时需要修改距离标号，通过增加一些弧来得到允许路 时间复杂度：o(n^2*m) 算法实现 练习 POJ 1149 - PIGS(较难) /JudgeOnline/problem?id=1149 绝对经典的构图题 POJ 1273 - Drainage Ditches(基础) /JudgeOnline/problem?id=1273 最大流入门 POJ 1459 - Power Network(基础) /JudgeOnline/problem?id=1459 基本构图 最大流问题的应用 Place the Robots（ZOJ1654） 问题描述 有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。 Place the Robots（ZOJ） 模型一 Place the Robots（ZOJ） 模型一 Place the Robots（ZOJ） 模型二 Place the Robots（ZOJ） 模型二 Place the Robots（ZOJ） 模型二 Place the Robots（ZOJ） 小结 例题：棋盘上的骑士 二分图最大独立集 设G=(v,e)是n阶图，如果G的顶点集合中U中任何两个顶点都不邻接，则称它为独立集。 最大独立集：在一个独立集中顶点的最大个数称为图G的独立数 设最大匹配边集是M,那么最大独立集个数|U|=|V|-|M| 棋盘上的骑士 将图中可以放置骑士的点看成二分图中的点，如果两个点互相攻击，那么就连一条边，最后求最大独立集的个数就是本题的解！ 最小路径覆盖 在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集． 　　由上面可以得出： 　　１.一个单独的顶点是一条路径； 　　２．如果存在一路径p1,p2,.....