网络流题选讲课件.pptx

上传人(卖家):三亚风情 文档编号:3393198 上传时间:2022-08-26 格式:PPTX 页数:29 大小:281.07KB
下载 相关 举报
网络流题选讲课件.pptx_第1页
第1页 / 共29页
网络流题选讲课件.pptx_第2页
第2页 / 共29页
网络流题选讲课件.pptx_第3页
第3页 / 共29页
网络流题选讲课件.pptx_第4页
第4页 / 共29页
网络流题选讲课件.pptx_第5页
第5页 / 共29页
点击查看更多>>
资源描述

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

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(网络流题选讲课件.pptx)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|