I题 首先看到题目数据范围很小,发现我们可以 的去检验任意两个数能不能同时被选中。这种关系很自然地让我们把这个题等价转换为 在一个无向图中,去选择顶点,有边相连的点不能同时选,这恰是二分图的等价定义! 那么现在的问题就是二分图中的最小点覆盖问题:我们想找到最少的一些点,使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是,删除包含这些点的边,可以删掉所有边。 我们就是要删除最少的点,使得剩下的点没有边(即二者不能同时被选中)相连 然后上定理 König定理: 一个二分图中的最大匹配数等于这个图中的最小点覆盖数 那么本题答案总点数二分图中的最大匹配数 其实通过观察可以发现 奇偶性相同的...