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