網(wǎng)絡(luò)流題選講-精選課件

1、網(wǎng)絡(luò)流題選講清華大學(xué) 計(jì)03 李宇亮狼和羊的故事n*m的網(wǎng)格每個(gè)格子：狼、羊、空要造籬笆，把狼和羊隔開，籬笆只能建在相鄰兩個(gè)格子之間。問最少多少籬笆？WSWSSWNOI2009 浙江省選題最小割WSWSSW1+Transform Matrix兩個(gè)n*m的01矩陣A和B對A進(jìn)行若干次操作，使得A變成和B一樣一次操作：交換A中相鄰兩個(gè)位置的元素每個(gè)格子(i,j)最多被操作count(i,j)次問最少操作次數(shù)001101011010100110100001111010011010010110101001011001011010100101010101101010010011010110101001T

2、opCoder srm407 division I level 3先不考慮count限制一次操作 = 移動(dòng)一個(gè)1，代價(jià)為1給定1的初始和最終位置，用最少的步數(shù)移動(dòng)對A中所有為1的點(diǎn)i，連邊(s,i)，容量為1，費(fèi)用為0對B中所有為1的點(diǎn)i，連邊(i,t)，容量為1，費(fèi)用為0相鄰的點(diǎn)連邊，容量為+，費(fèi)用為1考慮count1、若Ai,j=Bi,j，必被操作偶數(shù)次，移入一次，移出一次。所以點(diǎn)容量為counti,j/22、若Ai,j=1，Bi,j=0，移出比移入多一次。點(diǎn)容量為(counti,j+1)/23、若Ai,j=0，Bi,j=1，移入比移出多一次。點(diǎn)容量為(counti,j+1)/2。費(fèi)用為0

3、Road數(shù)列h修改，使之滿足：相鄰項(xiàng)差小于d總修改代價(jià)為 |hi|NOI2009 湖南省選題有別的算法，但是可以用網(wǎng)絡(luò)流做令ai=hi-hi+1hi加1 ai-1減1 且 ai加1。將a重新分配，使得每個(gè)a都在-d,d范圍內(nèi)。每個(gè)ai抽象為點(diǎn)特殊情況：修改h1(hn)只影響a1(an-1)，所以a1和an-1會(huì)憑空多1或少1憑空多1，從源點(diǎn)來，從s向1和n-1連邊， 容量+ ，費(fèi)用1類似，從1和n-1向t連邊，容量 + ，費(fèi)用1最小費(fèi)用可行流建設(shè)烏托鄉(xiāng)一張圖，有特殊點(diǎn)和一般點(diǎn)每條邊的端點(diǎn)中至少一個(gè)特殊點(diǎn)每個(gè)點(diǎn)有權(quán)值L，特殊點(diǎn)可以修改，代價(jià)為c*|Li|邊(i,j)要計(jì)算代價(jià)，為e*|Li-Lj

4、|求minc*|Li|+e*|Li-Lj|L只能為120的整數(shù)有道難題2019總決賽題j為一般點(diǎn)，且與i有邊再考慮特殊點(diǎn)之間的邊簡單情況：邊(1,2)、(2,3)，只有4種取值點(diǎn)1點(diǎn)2點(diǎn)31234取值L1=4，L2=2，L3=3代價(jià)：e*(2+1)+c*costiLi相差2層相差1層點(diǎn)1點(diǎn)2點(diǎn)31234取值點(diǎn)1點(diǎn)2點(diǎn)3最小割cost1,2cost1,3cost1,4cost1,1cost2,2cost2,3cost2,4cost2,1cost3,2cost3,3cost3,4cost3,1eeeeeeeecost1,5cost2,5cost3,5錦標(biāo)賽單循環(huán)，無平局，勝利最多奪冠，已知部分比賽

5、結(jié)果問哪些人可能奪冠算法藝術(shù)與信息學(xué)競賽枚舉讓誰奪冠，他剩下所有比賽均獲勝二分余下選手最多獲勝局?jǐn)?shù)k合理分配每局的勝利方剩下的每局比賽抽象為點(diǎn)，每個(gè)選手抽象為點(diǎn)比賽向?qū)?yīng)2個(gè)選手連邊，容量1設(shè)選手i已獲勝wi局，則i向T連邊容量為k-wiS向比賽點(diǎn)連容量1的邊志愿者招募N天第i天需要ai個(gè)志愿者M(jìn)類志愿者，每類人數(shù)無限第i類從第si天工作到第ti天，費(fèi)用ci求最小花費(fèi)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每個(gè)X、Y只出現(xiàn)2次，且正負(fù)各一次從一個(gè)點(diǎn)流出，一個(gè)點(diǎn)流入X1-Y1-2=0Y1+X2-Y2-1=0-X1+Y2+X3-Y3-1=0-X2-X3+Y3+4=0X、Y抽象為邊等式為流量平衡，抽象為點(diǎn)求最小費(fèi)用最大流ST容量+費(fèi)用ci容量+費(fèi)用0容量為對應(yīng)常數(shù)費(fèi)用0最長k可重區(qū)間N個(gè)開區(qū)間取若干個(gè)，使得沒有超過k個(gè)區(qū)間覆蓋同一點(diǎn)問：取得的區(qū)間長度和的最大值