国家集训队2002论文集 金恺.ppt

《国家集训队2002论文集 金恺.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈网络流算法的应用湖南省长沙市长郡中学金恺关键字：网络流、构造、优化【正文】【引言】【小结】浅谈网络流算法的应用引言图论算法在信息学竞赛当中扮演着相当重要的角色，它的分支之多、应用范围之广令所有其它算法都望尘莫及。而网络流算法正是图论算法中的一个重要分支，它特点突出、作用显著，因此应用范围十分广范，在近年来的各级别信息学竞赛中更是层出不穷，并且它还将占据着越来越重要的地位。本文旨在通过剖析若干应用实例，逐步阐述网络流算法的构造、优化原则和方法，对网络流算法作更深入、更彻底的认识。正文浅谈网络流算法的应用相信大家早已对网络

2、流算法的轮廓以及解法都进行了研究，这里只是我在平时做题过程中的一些体会，主要针对它的应用范围、具体应用方法以及诸多的优化技巧。例一例三例四例二赛车问题餐厅问题终极情报网列车调度例一赛车问题阿P与阿Q都是四驱车好手，他们各有N辆四驱车。为了一比高下，他们约好进行一场比赛。这次比赛共有M个分站赛，赢得分站赛场次多的获得总冠军。每个分站赛中，两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能，但由于种种原因（如相互之间的干扰），性能并不是决定胜负的唯一指标，有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种

3、高智能机器，只要给定两辆四驱车，就能立刻判断谁会赢，在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了，并且还把输赢表输入了电脑。另外，由于比赛的磨损，每辆四驱车都有自己的寿命（即它们能参加分站赛的场次），不同的四驱车寿命可能不同，但最多不会超过50场。两辆四驱车最多只能交手一次。现给定N、M（1<=N<=100，1<=M<=1000）、N*N的一个输赢表、每辆四驱车的寿命，并假设每次分站赛两人都有可选的赛车，请你计算一下阿P最多能够赢得多少个分站赛。问题描述构图优化例一赛车问题问题描述构图优化1、建立N个点代表

4、阿P的N辆车，分别以1到N标号；2、建立N个点代表阿Q的N辆车，分别以N+1到2N标号；3、如果阿P的第I辆车能够跑赢阿Q的第J辆车，则加一条弧IN+J，容量为1，表示两辆四驱车最多只能交手一次；4、增加一个源点S，S与1到N中的每一个结点I都连一条弧SI，容量为阿P的第I辆车的寿命；5、增加一个汇点T，N+1到2N中的每一个结点N+J到T都连一条弧N+JT，容量为阿Q的第J辆车的寿命；6、再增加一个源点S2，加一条弧S2S，容量为M，表示最多M场分站赛。例一赛车问题问题描述构图优化例一赛车问题问题描述构图优化普通

5、算法：保存流量与容量就需要（2N+3）*（2N+3）*2Bits优化：总共只有四类弧：1、S2S2、SI(i∈1..N)3、IJ(i∈1..N，j∈N+1..2N)4、JT(j∈N+1..2N)最多也不过1+N+N+N*N=（N+1）*（N+1）条弧S2这个源点与S2S这条弧都可以不要，只需规定最多扩展M次流量即可例二列车调度某货运车站有n（n≤20）个车道，由于车道的长度有限，每个车道在某一时刻最多只能停靠一列货运列车。车站正常运行后，每天将有m（m≤100）列货运列车从车站经过，其中第i列列车到达车站的时间为

6、Reach[i]，列车上装有价值Cost[i]的货物。如果准许列车i进站，则BackStreet车站将获得1%×Cost[i]的收益，但由于货物的搬运时间，该列车将在车站停留一段时间Stay[i]，这段时间内，列车将占用车站中的某一个车道；否则列车直接出站，但这样车站将得不到一分钱。你的任务就是：合理的安排列车的进站与出站，使得车站的总获利最大。{如果列车a从第i车道离开时，列车b刚好到站（即Reach[a]+Stay[a]=Reach[b]），则它不能进入第i车道。}问题描述构图优化例二列车调度问题描述构图优化例二列车调

7、度问题描述构图优化例二列车调度问题描述构图优化建图方法：1、将每一列列车拆成两个点，如第i列列车拆成点i和i'；i到i'之间加一条容量为1，费用为1%×Cost[i]的弧ii'；{若ii'的弧的流量为1，则表示该列火车进站，并获得1%×Cost[i]}2、增加一个源点S，S与每个点i连一条容量为1费用为0的弧Si；{如果Si的流量为1，则表示列车i作为某个车道的第一列入站的列车}3、再增加一个源点S’，S’S的容量为n，表示有n个车道；4、增加一个汇点T，每个点i'与T连一条容量为1费用为0的弧i'T；{如果i

8、’T的流量为1，则表示列车i作为某个车道的最后一列入站的列车}5、对于所有的i和j（i≠j，且i，j∈1..m）,如果Reach[i]+Stay[i]