Siyuan

「Codeforces 1199E」Matching vs Independent Set
「Codeforces 1199E」Matching vs Independent Set
扫描右侧二维码阅读全文
03
2019/08

「Codeforces 1199E」Matching vs Independent Set

题目链接:Codeforces 1199E

给定一个由 $3 \cdot n$ 个点、$m$ 条边组成的图。你需要找到一组大小为 $n$ 的边的匹配,或者找到一组大小为 $n$ 的独立集。

一组边的匹配表示不存在两条边拥有一个共同的点。

一组独立集表示不存在两个点被同一条边相连。

如果能找到一组边的匹配,输出 Matching 和方案;如果能找到一组独立集,输出 IndSet 和方案;否则输出 Impossible

本题有 $T$ 组数据。

数据范围:$1 \le \sum n \le 10 ^ {5}$,$0 \le \sum m \le 5 \times 10 ^ {5}$。


Solution

首先考虑 $3 \cdot n$ 个点有什么性质?如果存在一组不小于 $n$ 的匹配,那么这组匹配一定对应着不小于 $2n$ 个点——找到一组匹配;如果在某一时刻,按顺序加入匹配时找不到下一个匹配而此时的匹配数量少于 $n$ 个,那么剩下的点一定多于 $n$ 个且两两没有边相连——找到一组独立集

所以不存在无解情况。

时间复杂度:$\mathcal O(\sum n + \sum m)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5, M = 5e5 + 5;

int T, n, m, k;
bool dn[N], dm[M];

int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++) {
        scanf("%d%d", &k, &m), n = 3 * k;
        std::fill(dn + 1, dn + n + 1, false);
        std::fill(dm + 1, dm + m + 1, false);
        for (int i = 1, u, v; i <= m; i++) {
            scanf("%d%d", &u, &v);
            if (dn[u] || dn[v]) continue;
            dm[i] = dn[u] = dn[v] = true;
        }
        int cn = 0, cm = 0;
        for (int i = 1; i <= n; i++) cn += (dn[i] ? 0 : 1);
        for (int i = 1; i <= m; i++) cm += (dm[i] ? 1 : 0);
        if (cm >= k) {
            printf("Matching\n");
            for (int i = 1, cnt = 0; cnt < k; i++) {
                if (dm[i]) printf("%d%c", i, " \n"[++cnt == k]);
            }
        } else if (cn >= k) {
            printf("IndSet\n");
            for (int i = 1, cnt = 0; cnt < k; i++) {
                if (!dn[i]) printf("%d%c", i, " \n"[++cnt == k]);
            }
        } else {
            printf("Impossible\n");
        }
    }
    return 0;
}

发表评论