文档介绍：浅谈网络流算法的应用
湖南省长沙市长郡中学金恺
关键字: 网络流、构造、优化
【正文】
【引言】
【小结】
浅谈网络流算法的应用
引言
图论算法在信息学竞赛当中扮演着相当重要的角色,它的分支之多、应用范围之广令所有其它算法都望尘莫及。而网络流算法正是图论算法中的一个重要分支,它特点突出、作用显著,因此应用范围十分广范,在近年来的各级别信息学竞赛中更是层出不穷,并且它还将占据着越来越重要的地位。
本文旨在通过剖析若干应用实例,逐步阐述网络流算法的构造、优化原则和方法,对网络流算法作更深入、更彻底的认识。
正文
浅谈网络流算法的应用
相信大家早已对网络流算法的轮廓以及解法都进行了研究,这里只是我在平时做题过程中的一些体会,主要针对它的应用范围、具体应用方法以及诸多的优化技巧。
例一
例三
例四
例二
赛车问题
餐厅问题
终极情报网
列车调度
例一
赛车问题
阿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最多能够赢得多少个分站赛。
问题描述
构图
优化
例一
赛车问题
问题描述
构图
优化
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辆车的寿命;
5、增加一个汇点T,N+1到2N中的每一个结点N+J到T都连一条弧N+JT,容量为阿Q的第J辆车的寿命;
6、再增加一个源点S2,加一条弧S2S,容量为M,表示最多M场分站赛。
例一
赛车问题
问题描述
构图
优化
例一
赛车问题
问题描述
构图
优化
普通算法:保存流量与容量就需要(2N+3)*(2N+3)*2Bits
优化:总共只有四类弧:
1、S2S 2、SI(i∈1..N)
3、IJ(i∈1..N,j∈N+1..2N) 4、 JT(j∈N+1..2N)
最多也不过1+N+N+N*N=(N+1)*(N+1)条弧
S2这个源点与S2S这条弧都可以不要,只需规定最多扩展M次流量即可
例二
列车调度
某货运车站有n(n≤20)个车道,由于车道的长度有限,每个车道在某一时刻最多只能停靠一列货运列车。车站正常运行后,每天将有m(m≤100)列货运列车从车站经过,其中第i列列车到达车站的时间为Reach[i],列车上装有价值Cost[i]的货物。
如果准许列车i进站,则BackStreet车站将获得1%×Cost[i]的收益,但由于货物的搬运时间,该列车将在车站停留一段时间Stay[i],这段时间内,列车将占用车站中的某一个车道;否则列车直接出站,但这样车站将得不到一分钱。
你的任务就是:合理的安排列车的进站与出站,使得车站的总获利最大。
{如果列车a从第i车道离开时,列车b刚好到站(即Reach[a]+Stay[a] =Reach[b]),则它不能进入第i车道。}
问题描述
构图
优化
例二
列车调度
问题描述
构图
优化