尚未解答計算數學 Problem Solving- UVA10505-Montesco vs Capuleto
計算數學 Problem Solving- UVA10505-Montesco vs Capuleto
想問一下這題的測資部份，ubug 提供的測資只有一筆，並且如下附註：
Note : Don't assume that the number of enemies is always less than N.
最後查閱了網上其他的解答，題目要做二分圖匹配(刪除矛盾關係？)
最近練習利用 DisjointSetUnion 的 Union-Find 處理 Bipartite Graph 的問題。
主要是透過 UVa-10158 設定敵對關係的概念將相連的兩點分屬不同的兩群。
=== 能完成的題目似乎需要建立在形成二分圖的前提 ===
UVa-10004：判斷是否能形成二分圖？
ZJ-c889 ：可以形成二分圖時可以覆蓋的最大點數？
=== 無法完成 ===
UVa-00193：一樣是求最大的覆蓋點數，但差異是無法形成二分圖這點。
必須退回到暴力法實作，遞迴+剪枝，這邊也想問說能否透過DSU解出來？
回到 UVa-10505，題目給定的號碼會超過 N 嘛？ >> 測資會，所以直接無視就好
這題處理矛盾關係時是整個 component 都無視。換句話說，component 若可以變成
Bipartition Graph 時就加上最多的塗黑點，但出現矛盾時則無視。
舉個例子：
4
1 2
1 3
1 1
0
{1,2,3} 是一個無法形成 Bipartition 的 component 就無視，但{4} 自成一組可計算。
所以答案輸出 1 。
自己回自己的文( 好邊緣啊... OAQ )
--
0個答案
計算數學 Problem Solving- UVA10505-Montesco vs Capuleto
