冬令營預(yù)備網(wǎng)絡(luò)流與匹配

網(wǎng)絡(luò)流與匹配網(wǎng)絡(luò)流、匹配的基本概念網(wǎng)絡(luò)流、匹配的基本算法建模舉例綱要網(wǎng)絡(luò)流

定義

定義

定義

基本算法I增廣路算法：不斷在殘留網(wǎng)絡(luò)中尋找增廣路進(jìn)行增廣，直到找不到增廣路時算法結(jié)束。例如：深度優(yōu)先搜索廣度優(yōu)先搜索（Edmonds-Karp）標(biāo)號法（SAP）（間隙優(yōu)化）基本算法II

基本算法II層次圖中的網(wǎng)絡(luò)流算法：不同于之前的增廣路算法，這類算法每次可以查出很多條增廣路。主要方法是通過構(gòu)建網(wǎng)絡(luò)層次圖并在其中尋找增廣路來實(shí)現(xiàn)。例如：MPLADinicMPM基本算法III

基本算法III預(yù)流推進(jìn)算法詳見算法導(dǎo)論及moonancient的代碼?；舅惴↖V二分圖匹配N個人，M件任務(wù)。每個人能勝任M件任務(wù)中的若干件。已知每件任務(wù)只需要一個人來完成，每個人也只能完成一件任務(wù)。問，是否存在一種安排使得：每個人都有任務(wù)每個任務(wù)都有人去做同時滿足上面兩個條件簡單例子

基本算法I

基本算法II

定義

基本算法III

基本算法IV

基本算法V建模舉例FJ在修建擠奶機(jī)，但是不想被牛發(fā)現(xiàn)。在修建過程中，他要去擠奶機(jī)T次。農(nóng)場是N<=200個頂點(diǎn)的無向圖，有<=40000條道路（允許重邊），F(xiàn)J想去擠奶機(jī)T次（從頂點(diǎn)1出發(fā)，且不需要考慮返回），每次的每個道路都不能重復(fù)。安排這些路徑，使得經(jīng)過的所有單個道路中最長的一條最短。POJ2455SecretMilkingMachine有N<=1000頭奶牛和B<=20個牛棚。每個牛棚都有一定的容量。每個奶牛都給每個牛棚排了順序，最喜歡哪個，其次是哪個……求一種可行的分配方案，使得所有奶牛選擇牛棚的名次差最?。词顾麄兌歼x了最不喜歡的也可以）。POJ3189SteadyCowAssignmentF<=200個擋雨棚，每個擋雨棚有各自的容量。有些擋雨棚之間有路徑相連，路徑可以認(rèn)為無限寬并且通過需要一定的時間。一開始一些擋雨棚附近有一定數(shù)量的奶牛，問至少需要多少時間，才能使得每一頭奶牛都找到合適的擋雨棚。POJ2391OmbrophobicBovines一場比賽由N<=30個代表隊(duì)參與。每個隊(duì)伍都要和其他隊(duì)伍比賽一次。勝一場比賽得1分，輸則得0分。現(xiàn)在已經(jīng)決出一些場次的勝負(fù)，問哪些隊(duì)伍可能奪冠？聯(lián)賽對于一個N行、M列的0-1矩陣，規(guī)定在第i行中1的個數(shù)恰為Ri，在第j列中1的個數(shù)恰為Cj個，每一行、每一列最多可以有一個格子指定為0。問是否存在一種滿足條件的0-1矩陣。N,M<=1000，每個測試點(diǎn)最多10組數(shù)據(jù)2006年江蘇省選拔賽矩陣游戲IBM公司要運(yùn)送一批貨物從A星球到B星球。有些星球之間有雙向的傳送門，但是每天每個傳送門至多只能使用一次。問至少需要多少天，才能把K個貨物全部送到。N<=50,K<=50,M<=200。POJ1895BringThemThere有N個學(xué)生要去參觀M個學(xué)校，要求每個學(xué)生至多只能參觀一個學(xué)校（也可以一個學(xué)校都不參觀）。分別給出每個學(xué)生愿意參觀哪些學(xué)校，求一個滿足每個學(xué)校至少有兩個學(xué)生參觀的方案，或輸出符合條件的方案不存在。限制：M≤N≤200。SGU242Student’sMorning給出一個含N個頂點(diǎn)的有向無環(huán)圖G。用盡量少的不相交路徑覆蓋G的所有頂點(diǎn)，即每個頂點(diǎn)嚴(yán)格屬于一條路徑。允許路徑的長度為0，即只含一個頂點(diǎn)。最小路徑覆蓋給出一個帶權(quán)二分圖，其中X部和Y部各有N個頂點(diǎn)。求一個完備匹配，滿足匹配邊中權(quán)值最大的邊的權(quán)值盡量小。最小最大匹配國王有N個兒子，每個兒子都喜歡一些女孩?，F(xiàn)在每個兒子要娶一個女孩（一個女孩只能嫁給國王的一個兒子）。每個兒子有一個權(quán)值A(chǔ)i，如果他娶的是自己喜歡的女孩，則滿意度為Ai，否則為0。求一個分配方案，使得所有兒子的滿意度之和最大。限制：N≤400。SGU210BelovedSons有T種餡料，每個匹薩都會正好包含其中的K種?，F(xiàn)在有C頭奶牛。每頭牛都有一個喜歡的餡料的集合，如果一個匹薩含有的所有餡料都屬于這個集合