oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

呵呵，四城的博客真是好東東

看得不是太懂，請(qǐng)問可以舉個(gè)例子嗎？

首先 我們相當(dāng)于做一個(gè)簡單測試（判線段相交的快速排斥實(shí)驗(yàn)的那種味道）我們把所有節(jié)點(diǎn)的入度和出度分別相加 如果入度和和出度和不相等 顯然不滿足圖的要求（因?yàn)槿我庖粭l邊必然產(chǎn)生一個(gè)入度和一個(gè)出度）。否則我們定義M = SUM(in-degree); 接下來的任務(wù)是對(duì)這M條邊作點(diǎn)的分配。 如果考慮網(wǎng)絡(luò)流的做法，由于每個(gè)點(diǎn)對(duì)應(yīng)著2個(gè)權(quán)值 in-degree, out-degree，一種常規(guī)的做法是將一個(gè)點(diǎn)A分成2個(gè)點(diǎn) 我們稱為A-in & A-out。然后我們建立一個(gè)source連接到所有的A-out點(diǎn) 再建立一個(gè)sink連接所有的A-in。這樣我們就可以成功的把indegree和outdegree作為各自的容量。也就是從source到A-out的capacity定為A的out-degree，A-in到sink的capacity定為A的in-degree。為什么要這樣建圖呢？實(shí)際上作為任何一個(gè)可能存在的邊 在我們的點(diǎn)一分為2之后 都應(yīng)該是從A-out到B-in的這樣一條邊 所以我們這樣建圖之后 就可以對(duì)任一點(diǎn)的out到任一點(diǎn)的in連上一條capacity為1的邊（無重邊的題目描述）然后run一次最大流 如果能夠正確得到M的最大流（實(shí)際上就會(huì)得到M條邊） 這樣就滿足了題目要求了　呵呵　從整個(gè)過程來看　這個(gè)和二分圖匹配是很像的　實(shí)際上　很多題目的網(wǎng)絡(luò)流建圖方案都與２分圖匹配有著關(guān)聯(lián)　^_^

好詭異的算法……

建立一個(gè)source連接到所有的A-out點(diǎn) 再建立一個(gè)sink連接所有的A-in。這樣我們就可以成功的把indegree和outdegree作為各自的容量。也就是從source到A-out的capacity定為A的out-degree，A-in到sink的capacity定為A的in-degree。

source是什么，sink又是什么？看不懂哎，求解答。。。

是網(wǎng)絡(luò)流中我們自己確定的2個(gè)特殊節(jié)點(diǎn)。
如果對(duì)網(wǎng)絡(luò)流算法比較陌生 我覺得看一下相關(guān)書籍比較好 :)

zan!