作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] UVA10505-Montesco vs Capuleto
时间Fri Dec 11 16:30:32 2020
想问一下这题的测资部份，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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1607675446.A.68F.html
※ 编辑: fatcat8127 (61.222.86.91 台湾), 12/27/2020 16:29:03