本文純屬YY……

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

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

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

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

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

YY完畢，歡迎開炮……


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