空地 草地
Empty Grass Wall
墙
空地 Empty
草地
Grass Wall
墙
【模型一】 在问题的原型中，草地，墙这些信息不是我们 所关心的，我们关心的只是空地和空地之间的联系。 因此，我们很自然想到了下面这种简单的模型： 以空地为顶点，有冲突的空地间连边，我们可 以得到右边的这个图 ：
例题1 NOIP2010，第三题 关押罪犯



将N个人分成两组，其中M对人有Ci的不 和谐值，如果有不和谐值为Ci的两人在 同一组，那么就会有Ci的不和谐值。 要求找出一个分组方案，使得最大不和 谐值最小。 N<=20000 M<=100000
例题解答




直接做不好下手 由于要求最大值最小，即一个上界，所 以我们可以二分这个上界 那么我们就能确定哪些人不能在一组(不 和谐值大于上界的) 我们新建一张图，把不能在一组的人之 间连边，此时我们只需判断这个图能否 构成二分图即可。 复杂度O(MlogM)，实现简单
残量网络与增广轨




残量网络G’=(V,E,C),其中V,E与原网络G 相同，C为G中的容量-当前流量（即剩余 可流量） 增广轨就是一条S-T的不包含可流量为0 的边的路径 许多最大流算法都是通过不断找增广轨 进行增广从而得到最大流 定理：当前流为最大流当且仅当无增广 轨
一个重要的问题
增广一次，增加1的流量后无增广轨了，而最大流却不是 1. 我们可以走1-2-4和1-3-4得到2的流量


完全匹配

匹配边的端点为所有图中顶点
二分图的判定


判定一个无向图能否构成二分图 算法：BFS，复杂度O(M) 我们从任一点开始，令其在二分图左边 ，然后开始BFS，每次搜到的点放对面即 可，直至所有点放完或出现矛盾 正确性： 对于每个连通量而言，一个点如果确定 ，其他点均确定，而这个点放左，放右 实际上是对称的方案
最大流流量=最小割容量

引理:对于任一可行流F和任一割K，均有
当所有割边满流时等号 设F*为最大流，P*为最小割 我们找到一个割集P
aK aK
F (S ) F ( K ) C ( K ) Cap( K )


由引理得 F * ( S ) Cap( P*) ( P, P)之间的边必然满流 对于 且由割与最小割的关系 F * (S ) Cap( P) Cap( P*) 所以 F * (S ) Cap( P*)
Hopcroft-Karp算法



借用Dinic分层思想 每次对二分图分层(把二分图看做网络) 再用匈牙利算法，但是每次只走 a标号+1=b标号的边 可以证明最多进行 N 次分层 每次用O(M)的时间找增广轨 复杂度 O( N * M ) 目前已知的最快二分图匹配算法
小结
时间复杂度 网络流算法 匈牙利算法 Hopcroft-Karp 算法 O(N2*M) O(N*M) O(N0.5*M) 代码长度 较长 短 中等 思维难度 较低 低 中等
例题解答


但是O(M^2)的判断太慢 考虑到平面图的性质：边数与点数同阶 （在本题中可以3*N-6条边作为上限，如 果超过则直接判非平面图） 所以复杂度为O(N^2*T)
网络流

现在想将一些物资从S运抵T，必须经过一些中转站。 连接中转站的是公路，每条公路都有最大运载量。 每条弧代表一条公路，弧上的数表示该公路的最大运 载量。最多能将多少货物从S运抵T？ V1 V3 4 7 4 1 2 S 4 6 T



平面图的判定不好做 考虑问题特殊性 1，每条边其实有 两种画法，在里面 或在外面 2，每条边在里面或 外面可能会与其他边在里面或外面矛盾 （如蓝色与绿色矛盾）
例题解答



我们把每条边在里面，在外面这两种选 择看成两个点，那么一共有2M个点 用O(M^2)的时间判断每两个点是否矛盾 如果矛盾就连条边(保证自己选了，则矛 盾的都不选，或自己不选，矛盾的必选) 我们把每条边在里面与在外面连条边 (保证两个选择只选一个) 那么如果这个图能构成二分图，则原问
1
1
2 3 4 5
水平方向的块编号 竖直方向的块编号
3 4
2
把每个横向块看作X部的点，竖向块看作Y部的点，若 两个块有公共的空地，则在它们之间连边。于是，问题转 化成这样的一个二分图：
由于每条边表示一个空地，有冲突的空地之间必有 公共顶点，所以问题转化为二分图的最大匹配问题。
例
赛车问题
问题描述
问题的求解目标是寻求图G的最大独立集，即求G的 独立数α (G)。一般图的α (G)是很难计算的。 独立集是原图点集的一个子集，其中任意两点之间 没有边。 显然这一模型不是属于一些特殊的图，给我们设计 算法带来很大的麻烦。
【模型二】
我们将每一行，每一列被墙隔开，且包含空地的连续区域称 作“块”。显然，在一个块之中，最多只能放一个机器人。我 们把水平方向的这些块编上号；同样，把竖直方向的块也编上 号。
S2这个源点与S2S这条弧都可以不要，只需规定最多扩展M次流量即可

则称之为网络流图，记为G = (V,E,C)
可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组 数满足下列三条件时称为这网络的可行流，用f表示它。 1. 流量限制 每一条弧(i,j)有fij≤Cij 2. 流量平衡 除源点S和汇点T以外的所有的点vi，恒有： ∑j(fij)= ∑k(fjk) 该等式说明中间点vi的流量守恒，输入与输出量相等。 3. 对于源点S和汇点T有 ， ∑i(fSi)= ∑j(fjT)= V(f) 该等式说明源点流出量等于汇点流入量等于网络流流量


B[j]:=true L[j]为0或者Find(L[j])为真 //L数组记录右边每点匹配的左边点

L[j]:=I ,find:=true,exit； //找到就退出，返回真

Find:=false; //没找到 End Function 主程序 For I:=1~N

Fillchar(B,0,sizeof(B)) If find(i) then inc(Ans);
阿 P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他 们约好进行一场比赛。
这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。
每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分 取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不 是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局 面。幸好有一种高智能机器，只要给定两辆四驱车，就能立刻判断谁会 赢，在总比赛前它就已经把阿 p的每辆车与阿q的每辆车都两两测试过了， 并且还把输赢表输入了电脑。 另外，由于比赛的磨损，每辆四驱车都有自己的寿命（即它们能参加 分站赛的场次），不同的四驱车寿命可能不同，但最多不会超过 50场。 两辆四驱车最多只能交手一次。 现给定N、M（1<=N<=100，1<=M<=1000）、N*N的一个输赢 表、每辆四驱车的寿命，并假设每次分站赛两人都有可选的赛车，请你 计算一下阿P最多能够赢得多少个分站赛。
由于匈牙利算法简单好写，并且实际表现非常优秀，所 以推荐优先选择匈牙利算法。
例题 机器人布阵
有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型 之一：空地、草地、墙。机器人只能放在空地上。在同 一行或同一列的两个机器人，若它们之间没有墙，则它 们可以互相攻击。问给定的棋盘，最多可以放置多少个 机器人，使它们不能互相攻击。
构
图
1、建立N个点代表阿P的N辆车，分别以1到N标号； 2、建立N个点代表阿Q的N辆车，分别以N+1到2N标号；
3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧IN+J， 容量为1，表示两辆四驱车最多只能交手一次； 4、增加一个源点S，S与 1到N中的每一个结点I都连一条弧SI， 容量为阿P的第I辆车的寿命；

复杂度为O(N^2*M)
二分图的最大匹配

算法一：网络流 算法二：匈牙利算法 算法三：Hopcroft-Karp算法
网络流算法解二分图最大匹配


对于二分图G 新建源点S，汇点T S连向左边所有点，容量为1 原图所有边容量为1 右边所有点连向T，容量为1 对此网络求最大流，最大流流量即为最 大匹配数。
反向弧




刚才产生的问题在于没有“后悔”的机 会 怎么解决？ 回溯搜索？复杂度上升至指数级。 我们给每条边增加一条反向弧 即对于(i,j,c)我们增加边(j,i,0) 当(i,j,c)被增广了X的流量后，我们把反 向弧的可流量增加X
割切


将所有点划分为两个点集。 其中S和T在不同点集 割的容量为两点集之间的边的容量和 右图割容量： 8+4+4+1 =17
例题2 HNOI 2010 Planar


给定一个图，此图有一个包含所有顶点 的环（可以认为1-2-3-..-N-1） 判断此图是否为平面图 平面图

若能将无向图G画在平面上，使得任意两条 边不相交（可以在端点重合），则为平面图

T组数据 T<=100 N<=200 M<=10000
例题解答
匈牙利算法

依然是找增广轨的思想 循环每个左边点

以此点为起点找增广轨 如果找到则增广

循环N个点，每次找增广轨最多要找M次 复杂度O(Nion Find(i):boolean 循环每个i邻接的点j