[問題] UVA10505-Montesco vs Capuleto

看板 Prob_Solve
作者
時間
留言 0則留言,0人參與討論
推噓 0  ( 0推 0噓 0→ )
想問一下這題的測資部份,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 ) --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.222.86.91 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1607675446.A.68F.html ※ 編輯: fatcat8127 (61.222.86.91 臺灣), 12/27/2020 16:29:03