DOCX《网络流题选讲》

网络流题选讲 清华大学 计03 李宇亮 狼和羊的故事 n*m的网格 每个格子:狼、羊、空 要造篱笆,把狼和羊隔开,篱笆只能建在相邻两个格子之间.

问最少多少篱笆? W ? S ? ? ? ? ? ? W S ? S W NOI2009 浙江省选题 最小割 W ? S ? ? ? ? ? ? W S ? S W

1 +∞ +∞ +∞ +∞ +∞ +∞ Transform Matrix 两个n*m的01矩阵A和B 对A进行若干次操作,使得A变成和B一样 一次操作:交换A中相邻两个位置的元素 每个格子(i,j)最多被操作count(i,j)次 问最少操作次数

0 0

1 1

0 1

0 1

1 0

1 0

1 0

0 1

1 0

1 0

0 0

0 1

1 1

1 0

1 0

0 1

1 0

1 0

0 1

0 1

1 0

1 0

1 0

0 1

0 1

1 0

0 1

0 1

1 0

1 0

1 0

0 1

0 1

0 1

0 1

0 1

1 0

1 0

1 0

0 1

0 0

1 1

0 1

0 1

1 0

1 0

1 0

0 1 TopCoder srm407 division I level

3 先不考虑count限制 一次操作 = 移动一个1,代价为1 给定1的初始和最终位置,用最少的步数移动 对A中所有为1的点i,连边(s,i),容量为1,费用为0 对B中所有为1的点i,连边(i,t),容量为1,费用为0 相邻的点连边,容量为+∞,费用为1 考虑count

1、若Ai,j=Bi,j,必被操作偶数次,移入一次,移出一次.所以点容量为counti,j/2

2、若Ai,j=1,Bi,j=0,移出比移入多一次.点容量为(counti,j+1)/2

3、若Ai,j=0,Bi,j=1,移入比移出多一次.点容量为(counti,j+1)/2. 费用为0 Road 数列h 修改,使之满足:相邻项差小于d 总修改代价为 Σ|Δh[i]| NOI2009 湖南省选题 有别的算法,但是可以用网络流做 令a[i]=h[i]-h[i+1] h[i]加1 ? a[i-1]减1 且a[i]加1. 将a重新分配,使得每个a都在[-d,d]范围内. 每个a[i]抽象为点 特殊情况:修改h[1](h[n])只影响a[1](a[n-1]),所以a[1]和a[n-1]会凭空多1或少1 凭空多1,从源点来,从s向1和n-1连边, 容量+∞ ,费用1 类似,从1和n-1向t连边,容量 +∞ ,费用1 最小费用可行流 建设乌托乡 一张图,有特殊点和一般点 每条边的端点中至少一个特殊点 每个点有权值L,特殊点可以修改,代价为c*|ΔL[i]| 边(i,j)要计算代价,为e*|L[i]-L[j]| 求min{c*Σ|ΔL[i]|+e*Σ|L[i]-L[j]|} L只能为1~20的整数 有道难题2010总决赛题 j为一般点,且与i有边 再考虑特殊点之间的边 简单情况:边(1,2)、(2,3),只有4种取值 点1 点2 点3

1 2

3 4 取值 L[1]'=4,L[2]'=2,L[3]'=3 代价:e*(2+1)+c*Σcost[i][L[i]'] 最小割 锦标赛 单循环,无平局,胜利最多夺冠,已知部分比赛结果 问哪些人可能夺冠 《算法艺术与信息学竞赛》 枚举让谁夺冠,他剩下所有比赛均获胜 二分余下选手最多获胜局数k 合理分配每局的胜利方 剩下的每局比赛抽象为点,每个选手抽象为点 比赛向对应2个选手连边,容量1 设选手i已获胜w[i]局,则i向T连边容量为k-w[i] S向比赛点连容量1的边 志愿者招募 N天第i天需要a[i]个志愿者 M类志愿者,每类人数无限 第i类从第s[i]天工作到第t[i]天,费用c[i] 求最小花费 NOI2008

3 3

2 3

4 //a[i]

1 2

2 //[1,2] c=2

2 3

5 //[2,3] c=5

3 3

2 //[3,3] c=2 X[1]>=2 X[1]+X[2]>=3 X[2]+X[3]>=4 X[1]>=2 X[1]+X[2]>=3 X[2]+X[3]>=4 X[1]-Y[1]-2=0 X[1]+X[2]-Y[2]-3=0 X[2]+X[3]-Y[3]-4=0 X[1]-Y[1]-2=0 X[1]+X[2]-Y[2]-3=0 X[2]+X[3]-Y[3]-4=0 0=0 X[1]-Y[1]-2=0 Y[1]+X[2]-Y[2]-1=0 -X[1]+Y[2]+X[3]-Y[3]-1=0 -X[2]-X[3]+Y[3]+4=0 X[1]-Y[1]-2=0 Y[1]+X[2]-Y[2]-1=0 -X[1]+Y[2]+X[3]-Y[3]-1=0 -X[2]-X[3]+Y[3]+4=0 每个X、Y只出现2次,且正负各一次 从一个点流出,一个点流入 X[1]-Y[1]-2=0 Y[1]+X[2]-Y[2]-1=0 -X[1]+Y[2]+X[3]-Y[3]-1=0 -X[2]-X[3]+Y[3]+4=0 X、Y抽象为边 等式为流量平衡,抽象为点 求最小费用最大流 S T 容量+∞ 费用c[i] 容量+∞ 费用0 容量为对应常数 费用0 最长k可重区间 N个开区间 取若干个,使得没有超过k个区间覆盖同一点 问:取得的区间长度和的最大值 线性规划与网络流24题 考虑用流量限制为k的最大费用最大流来做 先离散化 每个端点建立一个结点,并增加S和T S T 容量k 费用0 容量1 费用为区间长度 容量k 费用0 容量k 费用0