本文純屬YY……
今天多校聯合訓練三的C題，
http://acm.hdu.edu.cn/showproblem.php?pid=3861，題意歸結起來是在一個有向圖中求最小路徑覆蓋，也就是用盡量少的鏈去覆蓋整個圖，每個頂點必須屬于且只能屬于一條鏈。但是題意并未說明原圖無環。標程解法是強連通分量縮點，再求有向無環圖的最小路徑覆蓋。反例是：1->2,2->3,4->5,5->6,2->5,5->2。正解是2，123一組，456一組。
因為是要求路徑數最小，所以YY了一個上下界最小流的做法。構圖是將原來的點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'，限制了這個點必須經過一次。這條邊上的流量有兩個來源：其它的點B'，或者源點S，前者說明A和B在同一條鏈中，B是A的前驅，后者說明A是鏈的起點。同樣，這個流量有兩個去處：其它的點C'，或者匯點T，前者說明A和C在同一條鏈中，C是A的后繼，后者說明A是鏈的終點。
到達匯的每1單位流量，意味著一條鏈的終結。所以最小流就能讓鏈數最少。
YY完畢，歡迎開炮……
ps. 理論上說，以上方法肯定是錯的。要不然求Hamiltion通路就不是NP了＠。＠
posted on 2011-07-19 22:42
wolf5x 閱讀(947)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc 、
algorithm