網頁

2014年5月8日 星期四

UVa 10349 Antenna Placement

題意:
    如題目的圖,一個圓圈最多能圈住兩個'*',現在問一幅圖有n個'*',最少用多少個圓圈就能把所有'*'圈住?

想法:
    最大匹配問題,將圖上所有點分成兩群相間隔,例如
101010
010101
101010
    在編號1的'*'建一條邊連到S(Super Source),在編號'0'的'*'建一條邊連到T(Super Sink ),然後相鄰的'*'彼此也建一條邊,這些邊的容量都是1,建完邊後套一次最大流模板,就是最大匹配數。
    做最大匹配得到的結果不是真正的答案,例如*****五個'*'的最大匹配是2,答案則是(5-3),因此本題答案為(所有'*'數量-最大匹配數)。