网络流题选讲-精选课件

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

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

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

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

5、结果问哪些人可能夺冠算法艺术与信息学竞赛枚举让谁夺冠，他剩下所有比赛均获胜二分余下选手最多获胜局数k合理分配每局的胜利方剩下的每局比赛抽象为点，每个选手抽象为点比赛向对应2个选手连边，容量1设选手i已获胜wi局，则i向T连边容量为k-wiS向比赛点连容量1的边志愿者招募N天第i天需要ai个志愿者M类志愿者，每类人数无限第i类从第si天工作到第ti天，费用ci求最小花费NOI20193 32 3 4/ai1 2 2/1,2 c=22 3 5/2,3 c=53 3 2/3,3 c=2X1=2X1+X2=3X2+X3=4X1=2X1+X2=3X2+X3=4X1-Y1-2=0X1+X2-Y2-3=0X

6、2+X3-Y3-4=0X1-Y1-2=0X1+X2-Y2-3=0X2+X3-Y3-4=00=0X1-Y1-2=0Y1+X2-Y2-1=0-X1+Y2+X3-Y3-1=0-X2-X3+Y3+4=0X1-Y1-2=0Y1+X2-Y2-1=0-X1+Y2+X3-Y3-1=0-X2-X3+Y3+4=0每个X、Y只出现2次，且正负各一次从一个点流出，一个点流入X1-Y1-2=0Y1+X2-Y2-1=0-X1+Y2+X3-Y3-1=0-X2-X3+Y3+4=0X、Y抽象为边等式为流量平衡，抽象为点求最小费用最大流ST容量+费用ci容量+费用0容量为对应常数费用0最长k可重区间N个开区间取若干个，使得没有超过k个区间覆盖同一点问：取得的区间长度和的最大值