网络流算法介绍课件

网络算法介绍PPT网络算法介绍PPT网络流算法介绍1.基本概念2.最大流问题求解3.二分图匹配4.二分图最佳匹配关键词：源点、汇点、容量、流量、残量、费用、增广路径网络流算法介绍1.基本概念关键词：源点、汇点、容量、网络流问题类比：求最短路径 把实际问题的道路地图抽象为有向图，然后用一定算法求解最短路径。 我们也可以将一个有向图看作一个流网络来解决另一类型的问题。 匹配问题、运输问题、任务分配问题。。。网络流问题类比：求最短路径流网络定义（FlowNetwork）V表示整个图中的所有结点的集合.E表示整个图中所有边的集合.G=(V,E),表示整个有向图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有一个容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，则表示(u,v)不在网络中。如果原网络中不存在边(u,v)，则令c(u,v)=0对于每条边(u,v),有一个流量f(u,v).流网络定义（FlowNetwork）V表示整个图中的所有结流网络示例水源源点S蓄水池汇点T水管/边流速限制容量c流速/流量f流网络示例水源蓄水池水管/边流速限制容量c流速/流量f网络流三个性质容量限制：f(u,v)<=c(u,v)对称性：f(u,v)==-f(v,u)收支平衡:对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。只要满足这三个性质,就是一个合法的网络流.网络流三个性质容量限制：f(u,v)<=c(u,v)网络的流量、最大流一个合法的网络流量|f|定义为：从源点流出的流量 ∑f(s,v)流向汇点的流量 ∑f(v,t)|f|的最大值表示为最大流网络的流量、最大流一个合法的网络流量|f|定义为：流网络示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)图中不给出网络的流量|f|=5+3=8或等于5+2+1(汇点处)0<=|f|<=最大流流网络示例收支平衡容量限制f(v4,v6)=-f(v6,残量网络对于网络中的每一条边，计算容量与流量的差即表示为残量。R(u,v)=C(u,v)–F(u,v)形象的说，一条边的残量即为该边还能流过的流量。残量网络对于网络中的每一条边，计算容量与流量的差即表示为残量残量网络举例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原网络残量网络残量网络举例v1tsv2(2,2)(4,4)(2,4)(0,残量网络从残量网络中可以清楚地看到：因为存在边(s,v2)=3,则知道从S到v2还可以再增加2单位的流量；因为存在边(v1,t)=2,则从v1到t还可以再增加2单位的流量。v1tsv2232422残量网络从残量网络中可以清楚地看到：v1tsv2232422后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。但是从v1到s和原网络中的弧的方向相反。这样的弧称为后向弧。问题：有必要建后向弧线？tsv232422v1后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s为什么要建立后向弧在寻找最大流的过程中，有些弧的选择一开始可能就是错误的。所以在路径中加上后向弧，作为标记。当发现了另一条可增广的路径是并包含后向弧，意味这条路径对以前对这条弧顶选择进行取消后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为为什么要建立后向弧在寻找最大流的过程中，有些弧的选择一开始可增广路径在残量网络中，从源点S出发到汇点T的一条路径。增广路径上的最小残量表示该网络还可增加的额外流量。增广路径点集间的流量定义点集间的流量：f(X,Y)=∑∑f(x,y)则有：

f(X,X)=0 (流的对称性) f(X,Y)=-f(Y,X) (流的对称性) f(X∪Y,Z)=f(X,Z)+f(Y,Z) f(X,Y∪Z)=f(X,Y)+f(X,Z)x∈Xy∈Y点集间的流量定义点集间的流量：f(X,Y)=∑∑f(点集间的流量不包含s,t的点集，与它关联的边上的流量和为零证明：f(X,V)=∑{∑f(x,v)} =∑0 (流量收支平衡)

=0x∈Xv∈Vx∈X点集间的流量不包含s,t的点集，与它关联的边上的流量和为零x网络中的割割（S,T）由两个点集S,T组成，满足

1、S+T=V 2、源点在S集合中

3、汇点在T集合中

4、f(S,T)表示割的流量

5、c(S,T)表示割的容量最小切割时使c(S,T)最小的切割网络中的割割（S,T）由两个点集S,T组成，满足割的流量任意割的流量等于网络的流量证明：

f(S,T)=f(S,V)–f(S,S) =f(S,V)+0=f(s,V)+f(S-{s},V)=f(s,V)+0=|f|割的流量任意割的流量等于网络的流量割的流量网络的流量小等于任意割的容量证明：

|f|=f(S,T)=∑∑f(x,y) <=∑∑c(x,y)=c(S,T)所以有最小割等于最大流x∈Sy∈Tx∈Sy∈T割的流量网络的流量小等于任意割的容量x∈Sy∈Tx∈Sy∈T最小割最大流定理网络的最大流等于最小割f是网络的最大流残量网络中无可增广路径存在某个切割(S,T),使f=c(S,T)以上三个命题是等价的，证明之：最小割最大流定理网络的最大流等于最小割1—>2反证法假设残量网络中还有增广路径，增广路径上的流量至少为1由该路径增广后的流量>f与f是最大流矛盾1—>2反证法2—>3此时的残量网络中不存在s-t通路定义S为s可达的点集定义T为可达t的点集显然S＋T=V(S,T)中所有弧都满载，否则残量网络将不为0，使s-t有通路所以|f|=c(S,T)2—>3此时的残量网络中不存在s-t通路3—>1由|f|<=c(S,T)（任意割）当|f|==c(S,T)|f|为最大值 从上面的证明，我们可以得到求最大流从增广路径算法。 从2->3的证明给出了从最大流构造最小割的过程，即求出s的可达点集S， 再令T=V-S3—>1由|f|<=c(S,T)（任意割）求最大流的增广路算法每次用BFS找一条最短的增广路径；然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。 路径上的后向弧+流量值 路径上的前向弧-流量值当没有增广路时，算法停止，此时的流就是最大流。求最大流的增广路算法每次用BFS找一条最短的增广路径；最大流例题BOJ1154典型的最大流问题已知网络容量,求最大流量根据题意构图如下: 1为源点,M为汇点.

容量为题目已知给出,可能的情况是相同两个结点之间有多条水渠,将它们累加即可.

初始化流量网络为0,则残量网络即初始为容量网络.算法流程:

构图->求最大流->输出最大流最大流例题BOJ1154典型的最大流问题最大流例题BOJ1154寻找增广路boolfindload(){memset(visited,0,sizeof(visited));head=tail=0;queue[tail++]=s;while(head<tail){j=queue[head++];for(i=1;i<=m;i++)if(!visited[i]&&cap[j][i]>0)//cap为容量,本题可以直接表示为残量

{pre[i]=j;//路径标志

visited[i]=1;if(i==t)returntrue;//找到s-t通路

queue[tail++]=i;}returnfalse;}

最大流例题BOJ1154寻找增广路最大流例题BOJ1154求最大流intmaxflow(){inti,j,flow=0,min;//min为增广路径上的瓶颈流量;flow网络最大流

while(findload()){min=0x7ffffff;for(i=t;i!=s;i=pre[i])min<?=cap[pre[i]][i];//找增广路径的瓶颈流量

flow+=min;for(i=t;i!=s;i=pre[i])//更新路径上的流量

{cap[pre[i]][i]-=min;//前向弧加mincap[i][pre[i]]+=min;//后向弧减min}}returnflow;}最大流例题BOJ1154求最大流最大流模型构图对于求流网络最大流的算法我们可以有现成的模板套用，在实际问题中，如何去构图建立最大流模型才是解决问题的难点和关键。构图一般考虑下面几个要素: 1、问题是否符合求源点到目标点的所经过网络的等效最大流。

2、找准源点和汇点

3、源点和网络中的点，汇点和网络中点的关系。

4、网络中的个点的关系。

5、明确什么是容量、流量、残量。最大流模型构图对于求流网络最大流的算法我们可以有现成的模板套Leapin'Lizards题意:有一间房子,有n*m个pillars,第一个矩阵表示相应的pillars能跳几个Lizards,第二个矩阵表示哪个pillars上有Lizard.d表示能跳的最大范围.Lizard跳出边界就能逃跑,问最少还有几个Lizards跑不了.思路:拆点,最大流.将每个>0的pillars拆开,有L的点由源点向其引一条边,边容量为1,能跳出边界的点向汇点引边,边容量为无穷.其他题目:pku3498Leapin'Lizards题意:有一间房子,有n*m个CableTVNetwork题意:一个无向图,问去掉几个点使得其不连通.思路:最小点割集,根据最小割最大流定理求解.拆点,求最大流.因为此题没有明确的源点和汇点,所以要枚举源点和汇点,然后求最大流,最大流的最小值就是最小割的最小值.其他题目：POJ3469CableTVNetwork题意:一个无向图,问去掉几二分图二分图作为流网络的一个特例，我们既可以特别去讨论它，也可以从网络流的角度来理解它。定义：二分图又称二部图，它是一个无向图，图的顶点分成两个不相交的点集X,Y.

对于图中任意一条边的两端点分别来自不同点集。112233445二分图二分图作为流网络的一个特例，我们既可以特别去讨论它，也二分图匹配给定二分图G，在G的子图M中，M的任意两条边都不共点，则称M为G图的一个匹配。M中边数最大的子集称为G的最大匹配。如果在最大匹配中，边涵盖了图中所有的点，则这样的匹配为完美匹配。二分图匹配给定二分图G，在G的子图M中，M的任意两条边都不共匈牙利算法实际上它也是一种不断寻找增广路径的算法增广路径定义： 若path是图G中一条连通两个未匹配顶点(分别属于X,Y)的路径， 并且属M的边和不属M的边(即已匹配和待匹配的边)在Path上交替出现， 则称Path为相对于M的一条增广路径。匈牙利算法实际上它也是一种不断寻找增广路径的算法二分图增广路由增广路定义可以得出：

1、path的长度必为奇数，且第一条边和最后一条边为不匹配边。

2、path经过路径取反操作以后，得到比当前更大的匹配。

3、当找不到增广路径时候，得到的匹配即为最大匹配。与增广路求最大流算法很类似二分图增广路由增广路定义可以得出：最大流和二分图匹配实际上二分图可以改造成一个流网络把X，Y的边改成从X到Y的有向边，并赋值为1，表示从X到Y容量为1。添加源点s，s到X部每个点的容量都为1。添加汇点t，Y到t部每个点的容量都为1。以此建立的流网络求得到最大流，即为原二分图中的最大匹配数。最大流和二分图匹配实际上二分图可以改造成一个流网络最大流和二分图匹配对上述的流网络求最大流的增广路算法我们已经了解了。每次找增广路时必然是以条从s到t的通路，除去s到X,Y到t两条边，剩下的边必然是在原二分图中交替前进。前向弧表示尚未匹配的边后向弧表示已经匹配的边路径取反操作实际上是更新流量操作最大流和二分图匹配对上述的流网络求最大流的增广路算法我们已经二分图匹配的构图首先划分“对立”的两个集合明确每个匹配关系的含义明确最大匹配的意义从最大流的构图方法来入手二分图匹配的构图首先划分“对立”的两个集合二分图匹配例题BOJ1155中文题目,题意好理解构图:考虑将墙面看成一个国际象棋的棋盘,那么每块瓷砖贴在棋盘上必然占一格白格和一格黑格.用棋盘的黑色格子表示二分图X部用棋盘的黑色格子表示二分图Y部相邻的格子用一条边连接二分图匹配例题BOJ1155中文题目,题意好理解二分图匹配例题BOJ1155找增广路径intpath(intv)//从X部的V点找增广路径{ for(inti=1;i<=m;i++) { if(g[v][i]&&!visited[i])//找到未匹配边

{ visited[i]=true; if(match[i]==-1||path(match[i])==1) { match[i]=v;//路径取反操作

return1; } } } return0;}二分图匹配例题BOJ1155找增广路径二分图匹配例题BOJ1155求最大匹配

cnt=0;//最大匹配数

memset(match,-1,sizeof(match));for(i=1;i<=n;i++){memset(visited,0,sizeof(visited));cnt+=path(i);}二分图匹配例题BOJ1155求最大匹配Asteroids题意：有一种超级武器，能摧毁一行或一列上的物体，现在有n*n的图，k个物体，最少多少次摧毁。思路：覆盖问题，用最少的线覆盖所有的点，二分图匹配，以点为边，以行和列为点，有物体的点的行和列连边，进行二分图最大匹配。其他题目：pku146920602226Asteroids题意：有一种超级武器，能摧毁一行或一列上AirRaid题意：有n个点，k条有向边，无环。求最少几次将整个图遍历完，每个点只能走一次。思路：最小路径覆盖=n-最大匹配，构造二分图，求最大匹配。入点，出点构成二分图，若i，j之间有边，则i的出点向j的入点连边，每匹配一对点，说明该路径能覆盖两个点，所以最小路径覆盖数减一。相关：pku2594AirRaid题意：有n个点，k条有向边，无环。求最少几二分图最佳匹配在二分图中的每条边都带上一个权值，求权和最大的匹配就叫二分图最佳匹配。具体模型BOJ上1080，1084就是非常赤裸的最佳匹配模型。求二分图最佳匹配的算法。二分图最佳匹配在二分图中的每条边都带上一个权值，求权和最大的KM算法给出每个顶点可行顶标lx,ly，对于所有边e(i,j)都有lx[i]+ly[j]>=w[i][j];对于所有边e(i,j)在M中，都有

lx[i]+ly[j]==w[i][j];则M是G的最佳匹配KM算法给出每个顶点可行顶标lx,ly，对于所有边e(i,二分图最佳匹配先将一个未被匹配的顶点u做一次增广路，记下哪些结点被访问那些结点没有被访问。求出d=min{lx[i]+ly[j]-w[i,j]}其中i结点被访问，j结点没有被访问。调整lx和ly：对于访问过的x顶点，将它的可行标减去d，访问过的y顶点，将它的可行标增加d。修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。二分图最佳匹配先将一个未被匹配的顶点u做一次增广路，记下哪些算法流程(1)初始化可行顶标的值(2)用匈牙利算法寻找完备匹配(3)若未找到完备匹配则修改可行顶标的值(4)重复(2)(3)直到找到相等子图的完备匹配为止算法流程(1)初始化可行顶标的值二分图最佳匹配例题BOJ1080题目意思非常清晰构图非常明确,工作为X,人为YX到Y的权值已知求X到Y的最小匹配把X到Y的劝值改为负数,求最佳匹配后,再取负数,得到的就是最小匹配值.二分图最佳匹配例题BOJ1080题目意思非常清晰二分图最佳匹配例题BOJ1080找增广路径intfind(intv){inti,tmp;x[v]=1;for(i=0;i<n;i++)if(!y[i]&&lx[v]+ly[i]==map[v][i]){tmp=match[i];match[i]=v;y[i]=1;if(tmp==-1||find(tmp))return1;match[i]=tmp;}return0;}二分图最佳匹配例题BOJ1080找增广路径二分图最佳匹配例题BOJ1080intKM(){inti,j,k,d,ans;for(k=0;k<n;k++)while(1){memset(x,0,sizeof(x));memset(y,0,sizeof(y));if(find(k))break;//找完美匹配子图

for(d=MAX,i=0;i<n;i++)if(x[i])for(j=0;j<n;j++)if(!y[j])d<?=lx[i]+ly[j]-map[i][j];for(i=0;i<n;i++){if(x[i])lx[i]-=d;if(y[i])ly[i]+=d;}}for(ans=0,i=0;i<n;i++)ans+=map[match[i]][i];returnans;}/*可行顶标ly记为0，lx记为与x相连的边的权最大值*/memset(ly,0,sizeof(ly));memset(match,-1,sizeof(match));for(i=0;i<n;i++){lx[i]=-MAX;for(j=0;j<n;j++)lx[i]>?=map[i][j];}二分图最佳匹配例题BOJ1080intKM()/*可行顶总结网络流模型可以用来解决很多关于分配求最优值得问题，它的最大流，最小费用最大流求解算法我们已经大概了解。在更多的实际问题中，网络流模型的建立往往是难点。巧妙的建立一个模型往往能诞生一个优质的算法。总结网络流模型可以用来解决很多关于分配求最优值得问题，它的最Thankyou!网络流算法介绍课件网络算法介绍PPT网络算法介绍PPT网络流算法介绍1.基本概念2.最大流问题求解3.二分图匹配4.二分图最佳匹配关键词：源点、汇点、容量、流量、残量、费用、增广路径网络流算法介绍1.基本概念关键词：源点、汇点、容量、网络流问题类比：求最短路径 把实际问题的道路地图抽象为有向图，然后用一定算法求解最短路径。 我们也可以将一个有向图看作一个流网络来解决另一类型的问题。 匹配问题、运输问题、任务分配问题。。。网络流问题类比：求最短路径流网络定义（FlowNetwork）V表示整个图中的所有结点的集合.E表示整个图中所有边的集合.G=(V,E),表示整个有向图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有一个容量c(u,v)(c(u,v)>=0)如果c(u,v)=0，则表示(u,v)不在网络中。如果原网络中不存在边(u,v)，则令c(u,v)=0对于每条边(u,v),有一个流量f(u,v).流网络定义（FlowNetwork）V表示整个图中的所有结流网络示例水源源点S蓄水池汇点T水管/边流速限制容量c流速/流量f流网络示例水源蓄水池水管/边流速限制容量c流速/流量f网络流三个性质容量限制：f(u,v)<=c(u,v)对称性：f(u,v)==-f(v,u)收支平衡:对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。只要满足这三个性质,就是一个合法的网络流.网络流三个性质容量限制：f(u,v)<=c(u,v)网络的流量、最大流一个合法的网络流量|f|定义为：从源点流出的流量 ∑f(s,v)流向汇点的流量 ∑f(v,t)|f|的最大值表示为最大流网络的流量、最大流一个合法的网络流量|f|定义为：流网络示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)图中不给出网络的流量|f|=5+3=8或等于5+2+1(汇点处)0<=|f|<=最大流流网络示例收支平衡容量限制f(v4,v6)=-f(v6,残量网络对于网络中的每一条边，计算容量与流量的差即表示为残量。R(u,v)=C(u,v)–F(u,v)形象的说，一条边的残量即为该边还能流过的流量。残量网络对于网络中的每一条边，计算容量与流量的差即表示为残量残量网络举例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原网络残量网络残量网络举例v1tsv2(2,2)(4,4)(2,4)(0,残量网络从残量网络中可以清楚地看到：因为存在边(s,v2)=3,则知道从S到v2还可以再增加2单位的流量；因为存在边(v1,t)=2,则从v1到t还可以再增加2单位的流量。v1tsv2232422残量网络从残量网络中可以清楚地看到：v1tsv2232422后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。但是从v1到s和原网络中的弧的方向相反。这样的弧称为后向弧。问题：有必要建后向弧线？tsv232422v1后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s为什么要建立后向弧在寻找最大流的过程中，有些弧的选择一开始可能就是错误的。所以在路径中加上后向弧，作为标记。当发现了另一条可增广的路径是并包含后向弧，意味这条路径对以前对这条弧顶选择进行取消后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为为什么要建立后向弧在寻找最大流的过程中，有些弧的选择一开始可增广路径在残量网络中，从源点S出发到汇点T的一条路径。增广路径上的最小残量表示该网络还可增加的额外流量。增广路径点集间的流量定义点集间的流量：f(X,Y)=∑∑f(x,y)则有：

f(X,X)=0 (流的对称性) f(X,Y)=-f(Y,X) (流的对称性) f(X∪Y,Z)=f(X,Z)+f(Y,Z) f(X,Y∪Z)=f(X,Y)+f(X,Z)x∈Xy∈Y点集间的流量定义点集间的流量：f(X,Y)=∑∑f(点集间的流量不包含s,t的点集，与它关联的边上的流量和为零证明：f(X,V)=∑{∑f(x,v)} =∑0 (流量收支平衡)

=0x∈Xv∈Vx∈X点集间的流量不包含s,t的点集，与它关联的边上的流量和为零x网络中的割割（S,T）由两个点集S,T组成，满足

1、S+T=V 2、源点在S集合中

3、汇点在T集合中

4、f(S,T)表示割的流量

5、c(S,T)表示割的容量最小切割时使c(S,T)最小的切割网络中的割割（S,T）由两个点集S,T组成，满足割的流量任意割的流量等于网络的流量证明：

f(S,T)=f(S,V)–f(S,S) =f(S,V)+0=f(s,V)+f(S-{s},V)=f(s,V)+0=|f|割的流量任意割的流量等于网络的流量割的流量网络的流量小等于任意割的容量证明：

|f|=f(S,T)=∑∑f(x,y) <=∑∑c(x,y)=c(S,T)所以有最小割等于最大流x∈Sy∈Tx∈Sy∈T割的流量网络的流量小等于任意割的容量x∈Sy∈Tx∈Sy∈T最小割最大流定理网络的最大流等于最小割f是网络的最大流残量网络中无可增广路径存在某个切割(S,T),使f=c(S,T)以上三个命题是等价的，证明之：最小割最大流定理网络的最大流等于最小割1—>2反证法假设残量网络中还有增广路径，增广路径上的流量至少为1由该路径增广后的流量>f与f是最大流矛盾1—>2反证法2—>3此时的残量网络中不存在s-t通路定义S为s可达的点集定义T为可达t的点集显然S＋T=V(S,T)中所有弧都满载，否则残量网络将不为0，使s-t有通路所以|f|=c(S,T)2—>3此时的残量网络中不存在s-t通路3—>1由|f|<=c(S,T)（任意割）当|f|==c(S,T)|f|为最大值 从上面的证明，我们可以得到求最大流从增广路径算法。 从2->3的证明给出了从最大流构造最小割的过程，即求出s的可达点集S， 再令T=V-S3—>1由|f|<=c(S,T)（任意割）求最大流的增广路算法每次用BFS找一条最短的增广路径；然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。 路径上的后向弧+流量值 路径上的前向弧-流量值当没有增广路时，算法停止，此时的流就是最大流。求最大流的增广路算法每次用BFS找一条最短的增广路径；最大流例题BOJ1154典型的最大流问题已知网络容量,求最大流量根据题意构图如下: 1为源点,M为汇点.

容量为题目已知给出,可能的情况是相同两个结点之间有多条水渠,将它们累加即可.

初始化流量网络为0,则残量网络即初始为容量网络.算法流程:

构图->求最大流->输出最大流最大流例题BOJ1154典型的最大流问题最大流例题BOJ1154寻找增广路boolfindload(){memset(visited,0,sizeof(visited));head=tail=0;queue[tail++]=s;while(head<tail){j=queue[head++];for(i=1;i<=m;i++)if(!visited[i]&&cap[j][i]>0)//cap为容量,本题可以直接表示为残量

{pre[i]=j;//路径标志

visited[i]=1;if(i==t)returntrue;//找到s-t通路

queue[tail++]=i;}returnfalse;}

最大流例题BOJ1154寻找增广路最大流例题BOJ1154求最大流intmaxflow(){inti,j,flow=0,min;//min为增广路径上的瓶颈流量;flow网络最大流

while(findload()){min=0x7ffffff;for(i=t;i!=s;i=pre[i])min<?=cap[pre[i]][i];//找增广路径的瓶颈流量

flow+=min;for(i=t;i!=s;i=pre[i])//更新路径上的流量

{cap[pre[i]][i]-=min;//前向弧加mincap[i][pre[i]]+=min;//后向弧减min}}returnflow;}最大流例题BOJ1154求最大流最大流模型构图对于求流网络最大流的算法我们可以有现成的模板套用，在实际问题中，如何去构图建立最大流模型才是解决问题的难点和关键。构图一般考虑下面几个要素: 1、问题是否符合求源点到目标点的所经过网络的等效最大流。

2、找准源点和汇点

3、源点和网络中的点，汇点和网络中点的关系。

4、网络中的个点的关系。

5、明确什么是容量、流量、残量。最大流模型构图对于求流网络最大流的算法我们可以有现成的模板套Leapin'Lizards题意:有一间房子,有n*m个pillars,第一个矩阵表示相应的pillars能跳几个Lizards,第二个矩阵表示哪个pillars上有Lizard.d表示能跳的最大范围.Lizard跳出边界就能逃跑,问最少还有几个Lizards跑不了.思路:拆点,最大流.将每个>0的pillars拆开,有L的点由源点向其引一条边,边容量为1,能跳出边界的点向汇点引边,边容量为无穷.其他题目:pku3498Leapin'Lizards题意:有一间房子,有n*m个CableTVNetwork题意:一个无向图,问去掉几个点使得其不连通.思路:最小点割集,根据最小割最大流定理求解.拆点,求最大流.因为此题没有明确的源点和汇点,所以要枚举源点和汇点,然后求最大流,最大流的最小值就是最小割的最小值.其他题目：POJ3469CableTVNetwork题意:一个无向图,问去掉几二分图二分图作为流网络的一个特例，我们既可以特别去讨论它，也可以从网络流的角度来理解它。定义：二分图又称二部图，它是一个无向图，图的顶点分成两个不相交的点集X,Y.

对于图中任意一条边的两端点分别来自不同点集。112233445二分图二分图作为流网络的一个特例，我们既可以特别去讨论它，也二分图匹配给定二分图G，在G的子图M中，M的任意两条边都不共点，则称M为G图的一个匹配。M中边数最大的子集称为G的最大匹配。如果在最大匹配中，边涵盖了图中所有的点，则这样的匹配为完美匹配。二分图匹配给定二分图G，在G的子图M中，M的任意两条边都不共匈牙利算法实际上它也是一种不断寻找增广路径的算法增广路径定义： 若path是图G中一条连通两个未匹配顶点(分别属于X,Y)的路径， 并且属M的边和不属M的边(即已匹配和待匹配的边)在Path上交替出现， 则称Path为相对于M的一条增广路径。匈牙利算法实际上它也是一种不断寻找增广路径的算法二分图增广路由增广路定义可以得出：

1、path的长度必为奇数，且第一条边和最后一条边为不匹配边。

2、path经过路径取反操作以后，得到比当前更大的匹配。

3、当找不到增广路径时候，得到的匹配即为最大匹配。与增广路求最大流算法很类似二分图增广路由增广路定义可以得出：最大流和二分图匹配实际上二分图可以改造成一个流网络把X，Y的边改成从X到Y的有向边，并赋值为1，表示从X到Y容量为1。添加源点s，s到X部每个点的容量都为1。添加汇点t，Y到t部每个点的容量都为1。以此建立的流网络求得到最大流，即为原二分图中的最大匹配数。最大流和二分图匹配实际上二分图可以改造成一个流网络最大流和二分图匹配对上述的流网络求最大流的增广路算法我们已经了解了。每次找增广路时必然是以条从s到t的通路，除去s到X,Y到t两条边，剩下的边必然是在原二分图中交替前进。前向弧表示尚未匹配的边后向弧表示已经匹配的边路径取反操作实际上是更新流量操作最大流和二分图匹配对上述的流网络求最大流的增广路算法我们已经二分图匹配的构图首先划分“对立”的两个集合明确每个匹配关系的含义明确最大匹配的意义从最大流的构图方法来入手二分图匹配的构图首先划分“对立”的两个集合二分图匹配例题BOJ1155中文题目,题意好理解构图:考虑将墙面看成一个国际象棋的棋盘,那么每块瓷砖贴在棋盘上必然占一格白格和一格黑格.用棋盘的黑色格子表示二分图X部用棋盘的黑色格子表示二分图Y部相邻的格子用一条边连接二分图匹配例题BOJ1155中文题目,题意好理解二分图匹配例题BOJ1155找增广路径intpath(intv)//从X部的V点找增广路径{ for(inti=1;i<=m;i++) { if(g[v][i]&&!visited[i])//找到未匹配边

{ visited[i]=true; if(match[i]==-1||path(match[i])==1) { match[i]=v;//路径取反操作

return1; } } } return0;}二分图匹配例题BOJ1155找增广路径二分图匹配例题BOJ1155求最大匹配

cnt=0;//最大匹配数

memset(match,-1,sizeof(match));for(i=1;i<=n;i++){memset(visited,0,sizeof(visited));cnt+=path(i);}二分图匹配例题BOJ1155求最大匹配Asteroids题意：有一种超级武器，能摧毁一行或一列上的物体，现在有n*n的图，k个物体，最少多少次摧毁。思路：覆盖问题，用最少的线覆盖所有的点，二分图匹配，以点为边，以行和列为点，有物体的点的行和列连边，进行二分图最大匹配。其他题目：pku146920602226Asteroids题意：有一种超级武器，能摧毁一行或一列上AirRaid题意：有n个点，k条有向边，无环。求最少几次将整个图遍历完，每个点只能走一次。思路：最小路径覆盖=n-最大匹配，构造二分图，求最大匹配。入点，出点构成二分图，若i，j之间有边，则i的出点向j的入点连边，每匹配一对点，说明该路径能覆盖两个点，所以最小路径覆盖数减一。相关：pku2594AirRaid题意：有n个点，k条有向边，无环。求最少几二分图最佳匹配在二分图中的每条边都带上一个权值，求权和最大的匹配就叫二分图最佳匹配。具体模型BOJ上1080，1084就是非常赤裸的最佳匹配模型。求二分图最佳匹配的算法。二分图最佳匹配在二分图中的每条边都带上一个权值，求权和最大的KM算法给出每个顶点可行顶标lx,ly，对于所有边e(i,j)都有lx[i]+ly[j]>=w[i][j];对于所有边e(i,j)在M中，都有

lx[i]+ly[j]==w[i][j];则M是G