JSC2019 Qual E: Card Collector

把行列建成二分图,卡片是边;可行选择等价于伪森林,按权值降序用带环标记的并查集贪心求最大权伪森林。

来源 AtCoder JSC2019 Qualification E · 时间 2 s,空间 1024 MB · 标签 拟阵 / 贪心 / 并查集 / 伪森林

题目描述

有 𝐻 行 𝑊 列的网格,放置了 𝑁 张卡片。第 𝑖 张卡片在 (𝑅𝑖,𝐶𝑖),上面写着整数 𝐴𝑖;同一格可以有多张卡片。

先进行第一轮:每行至多选一张卡片。再进行第二轮:每列至多选一张卡片。最终选中的卡片取两轮的并集,求卡片上的整数之和的最大值。

1≤𝑁≤105,1≤𝐻,𝑊≤105,1≤𝐴𝑖≤105。

题解

把每一行、每一列分别建成一个点,得到二分图;第 𝑖 张卡片对应连接行 𝑅𝑖 与列 𝐶𝑖 的边,边权为 𝐴𝑖。

最终选中的卡片分成两类:

  • 第一轮按行选的卡片;
  • 第二轮按列选的卡片。

把第一类边分配给它的行端点,第二类边分配给它的列端点。每个行点、列点至多被分配一条边。反过来,若一个边集能这样把每条边分配给一个端点,且每个端点至多分到一条边,就可以按分配的端点所在侧分成两轮选择。

因此,一个卡片集合可行,当且仅当它对应的边集能定向到端点,使每个顶点的入度不超过 1。一个图存在这样的定向,当且仅当每个连通分量至多含一个环,也就是这个边集是伪森林。

问题于是转化为:在二分图中求最大权伪森林。

伪森林是 双循环拟阵 的独立集,因此可以按边权从大到小做拟阵贪心:能加入当前边集就加入。用带“是否已有环”标记的并查集维护连通分量:

  • 若一条边的两个端点属于不同分量:

    • 若两个分量都已有环,加入后会形成两个环,跳过;
    • 否则合并两个分量,新分量的环标记为两者的或。
  • 若两个端点属于同一分量:

    • 若该分量还没有环,加入这条边形成第一个环,保留并标记;
    • 若已经有环,加入会形成第二个环,跳过。

按边权降序执行,保留的边权和就是答案。

复杂度

排序 𝑂(𝑁log𝑁),并查集 𝑂((𝐻+𝑊+𝑁)𝛼(𝐻+𝑊)),空间 𝑂(𝑁+𝐻+𝑊)。

参考

源码位置