本文純屬YY……

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

因為是要求路徑數(shù)最小，所以YY了一個上下界最小流的做法。構(gòu)圖是將原來的點A0拆成兩個，A和A'。從A到A'連一條邊，下界和上界都為1。所有原來A0的出邊，都從A'出去，下界0，上界1.所有原來A0的入邊，都指向A。新建一個源點S，一個匯點T。從S到每個點A連一條邊，下界0，上界1。從每個A'到T連一條邊，下界0，上界1。

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

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

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

YY完畢，歡迎開炮……


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