网络流题选讲课件.pptx

1、狼和羊的故事vn*m的网格v每个格子：狼、羊、空v要造篱笆，把狼和羊隔开，篱笆只能建在相邻两个格子之间。v问最少多少篱笆？WSWSSWNOI2009浙江省选题v最小割WSWSSW1+TransformMatrixv两个n*m的01矩阵A和Bv对A进行若干次操作，使得A变成和B一样v一次操作：交换A中相邻两个位置的元素v每个格子(i,j)最多被操作count(i,j)次v问最少操作次数001101011010100110100001111010011010010110101001011001011010100101010101101010010011010110101001TopCodersrm

2、407divisionIlevel3v先不考虑count限制v一次操作=移动一个1，代价为1v给定1的初始和最终位置，用最少的步数移动v对A中所有为1的点i，连边(s,i)，容量为1，费用为0v对B中所有为1的点i，连边(i,t)，容量为1，费用为0v相邻的点连边，容量为+，费用为1v考虑countv1、若Ai,j=Bi,j，必被操作偶数次，移入一次，移出一次。所以点容量为counti,j/2v2、若Ai,j=1，Bi,j=0，移出比移入多一次。点容量为(counti,j+1)/2v3、若Ai,j=0，Bi,j=1，移入比移出多一次。点容量为(counti,j+1)/2。v费用为0Roadv数

3、列hv修改，使之满足：相邻项差小于dv总修改代价为|hi|NOI2009湖南省选题v有别的算法，但是可以用网络流做v令ai=hi-hi+1vhi加1ai-1减1且ai加1。v将a重新分配，使得每个a都在-d,d范围内。v每个ai抽象为点v特殊情况：修改h1(hn)只影响a1(an-1)，所以a1和an-1会凭空多1或少1v凭空多1，从源点来，从s向1和n-1连边，容量+，费用1v类似，从1和n-1向t连边，容量+，费用1v最小费用可行流建设乌托乡v一张图，有特殊点和一般点v每条边的端点中至少一个特殊点v每个点有权值L，特殊点可以修改，代价为c*|Li|v边(i,j)要计算代价，为e*|Li-L

4、j|v求minc*|Li|+e*|Li-Lj|vL只能为120的整数有道难题2010总决赛题j为一般点，且与i有边v再考虑特殊点之间的边v简单情况：边(1,2)、(2,3)，只有4种取值点1点2点31234取值vL1=4，L2=2，L3=3v代价：e*(2+1)+c*costiLi相差2层相差1层点1点2点31234取值点1点2点3v最小割cost1,2cost1,3cost1,4cost1,1cost2,2cost2,3cost2,4cost2,1cost3,2cost3,3cost3,4cost3,1eeeeeeeecost1,5cost2,5cost3,5锦标赛v单循环，无平局，胜利最多

5、夺冠，已知部分比赛结果v问哪些人可能夺冠算法艺术与信息学竞赛v枚举让谁夺冠，他剩下所有比赛均获胜v二分余下选手最多获胜局数kv合理分配每局的胜利方v剩下的每局比赛抽象为点，每个选手抽象为点v比赛向对应2个选手连边，容量1v设选手i已获胜wi局，则i向T连边容量为k-wivS向比赛点连容量1的边志愿者招募vN天v第i天需要ai个志愿者vM类志愿者，每类人数无限v第i类从第si天工作到第ti天，费用civ求最小花费NOI2008v33v234/aiv122/1,2c=2v235/2,3c=5v332/3,3c=2vX1=2vX1+X2=3vX2+X3=4vX1=2vX1+X2=3vX2+X3=4v

6、X1-Y1-2=0vX1+X2-Y2-3=0vX2+X3-Y3-4=0vX1-Y1-2=0vX1+X2-Y2-3=0vX2+X3-Y3-4=0v0=0vX1-Y1-2=0vY1+X2-Y2-1=0v-X1+Y2+X3-Y3-1=0v-X2-X3+Y3+4=0vX1-Y1-2=0vY1+X2-Y2-1=0v-X1+Y2+X3-Y3-1=0v-X2-X3+Y3+4=0v每个X、Y只出现2次，且正负各一次v从一个点流出，一个点流入vX1-Y1-2=0vY1+X2-Y2-1=0v-X1+Y2+X3-Y3-1=0v-X2-X3+Y3+4=0vX、Y抽象为边v等式为流量平衡，抽象为点v求最小费用最大流ST容量+费用ci容量+费用0容量为对应常数费用0最长k可重区间vN个开区间v取若干个，使得没有超过k个区间覆盖同一点v问：取得的区间长度和的最大值线性规划与网络流24题v考虑用流量限制为k的最大费用最大流来做v先离散化v每个端点建立一个结点，并增加S和TST1/11/21/2容量k费用0容量1费用为区间长度容量k费用0容量k费用0