本文純屬YY……

今天多校聯(lián)合訓(xùn)練三的C題，http://acm.hdu.edu.cn/showproblem.php?pid=3861，題意歸結(jié)起來(lái)是在一個(gè)有向圖中求最小路徑覆蓋，也就是用盡量少的鏈去覆蓋整個(gè)圖，每個(gè)頂點(diǎn)必須屬于且只能屬于一條鏈。但是題意并未說(shuō)明原圖無(wú)環(huán)。標(biāo)程解法是強(qiáng)連通分量縮點(diǎn)，再求有向無(wú)環(huán)圖的最小路徑覆蓋。反例是：1->2,2->3,4->5,5->6,2->5,5->2。正解是2，123一組，456一組。

因?yàn)槭且舐窂綌?shù)最小，所以YY了一個(gè)上下界最小流的做法。構(gòu)圖是將原來(lái)的點(diǎn)A0拆成兩個(gè)，A和A'。從A到A'連一條邊，下界和上界都為1。所有原來(lái)A0的出邊，都從A'出去，下界0，上界1.所有原來(lái)A0的入邊，都指向A。新建一個(gè)源點(diǎn)S，一個(gè)匯點(diǎn)T。從S到每個(gè)點(diǎn)A連一條邊，下界0，上界1。從每個(gè)A'到T連一條邊，下界0，上界1。

對(duì)這個(gè)新圖求最小流，即為原題所求。

YY的證明：
A->A'，限制了這個(gè)點(diǎn)必須經(jīng)過(guò)一次。這條邊上的流量有兩個(gè)來(lái)源：其它的點(diǎn)B'，或者源點(diǎn)S，前者說(shuō)明A和B在同一條鏈中，B是A的前驅(qū)，后者說(shuō)明A是鏈的起點(diǎn)。同樣，這個(gè)流量有兩個(gè)去處：其它的點(diǎn)C'，或者匯點(diǎn)T，前者說(shuō)明A和C在同一條鏈中，C是A的后繼，后者說(shuō)明A是鏈的終點(diǎn)。

到達(dá)匯的每1單位流量，意味著一條鏈的終結(jié)。所以最小流就能讓鏈數(shù)最少。

YY完畢，歡迎開(kāi)炮……


ps. 理論上說(shuō)，以上方法肯定是錯(cuò)的。要不然求Hamiltion通路就不是NP了＠。＠