JSC2019 Qual E: Card Collector
把行列建成二分图,卡片是边;可行选择等价于伪森林,按权值降序用带环标记的并查集贪心求最大权伪森林。来源 AtCoder JSC2019 Qualification E · 时间 2 s,空间 1024 MB · 标签 拟阵 / 贪心 / 并查集 / 伪森林
题目描述
有 行 列的网格,放置了 张卡片。第 张卡片在 ,上面写着整数 ;同一格可以有多张卡片。
先进行第一轮:每行至多选一张卡片。再进行第二轮:每列至多选一张卡片。最终选中的卡片取两轮的并集,求卡片上的整数之和的最大值。
,,。
题解
把每一行、每一列分别建成一个点,得到二分图;第 张卡片对应连接行 与列 的边,边权为 。
最终选中的卡片分成两类:
- 第一轮按行选的卡片;
- 第二轮按列选的卡片。
把第一类边分配给它的行端点,第二类边分配给它的列端点。每个行点、列点至多被分配一条边。反过来,若一个边集能这样把每条边分配给一个端点,且每个端点至多分到一条边,就可以按分配的端点所在侧分成两轮选择。
因此,一个卡片集合可行,当且仅当它对应的边集能定向到端点,使每个顶点的入度不超过 。一个图存在这样的定向,当且仅当每个连通分量至多含一个环,也就是这个边集是伪森林。
问题于是转化为:在二分图中求最大权伪森林。
伪森林是 双循环拟阵 的独立集,因此可以按边权从大到小做拟阵贪心:能加入当前边集就加入。用带“是否已有环”标记的并查集维护连通分量:
若一条边的两个端点属于不同分量:
- 若两个分量都已有环,加入后会形成两个环,跳过;
- 否则合并两个分量,新分量的环标记为两者的或。
若两个端点属于同一分量:
- 若该分量还没有环,加入这条边形成第一个环,保留并标记;
- 若已经有环,加入会形成第二个环,跳过。
按边权降序执行,保留的边权和就是答案。
复杂度
排序 ,并查集 ,空间 。
参考
- 题目链接:AtCoder JSC2019 Qual E Card Collector。
- 思路参考:Sshwy 做题总结。