UVa11419 SAM I AM

题意

一个R\times C的矩形上有N个点,你可以选择一些行列,要求选择的行列覆盖所有的点。求最小需要选择多少行列,要求输出任一方案。

分析

RC表示行列的点集,对于坐标为(x,y)的点,我们将R中的点xC中的y点连边。这样二分图中的一条边,它就表示了矩阵中的一个点,我们任务就转化为在二分图中找出尽量少的点组成点集S,使每条边都至少有一个点在S中。这样就转化为了二分图的最小点覆盖问题。
由König定理我们可以知道最小点覆盖=最大匹配。但是题目还要求输出方案,我们可以把匹配后的边分类讨论:

  1. 左未盖右盖:我们从左边的点出发找增广路,此时增广路的终点会是左边的已盖点或未盖点,这种情况我们选择增广路上在右边点集里的点优,因为点数少1
  2. 左盖右未盖:同理,我们选择增广路上在左边点集里的点优
  3. 左盖右盖:我们考虑完上面2类,说明左右两个匹配点都不在上面选择的点范围内,这时候我们可以在边的两端任选一个点

综合起来就是:从左边未盖点出发找增广路,将路径上所有点标记。答案就是左边点集未被标记的点和右边点集被标记的点。

当然,看过Matrix67的证明后就正真明白这是为什么了,其实我们不需要这么牵强的拼凑,这里大致写一写:
当我们得到最大匹配之后,这时考虑从右边的未匹配点出发找增广路,这时候找到的一定是不完整的增广路,我们将走过的点都标记一下,这时候左边的标记点和右边的未标记点构成了一个最小覆盖集。
我们先证明这样恰好覆盖集是|M|个点:容易发现我们选的点每个点都是匹配点,左边的点当然是,右边的点如果没有被标记那么它一定属于那种走不到的匹配点。
然后证明这样覆盖了所有的边:当前我们已经覆盖了所有左右端点都被标记的边和左右端点都没有被标记的边,下面我们来证明不存在左端点被标记而右端点不被标记和左端点不被标记而右端点被标记的边:

  • 左端点被标记而右端点不被标记:可以知道这个右端点一定是匹配点,那么这个左端点就不肯能是未匹配点(左边的未匹配点不可能被标记),则它是匹配点,既然这个匹配点被标记,说明当时走过来的是非匹配边,那么这个右端点不可能被标记。
  • 左端点不被标记而右端点被标记:若该边不是匹配边,那么右端点一定会被标记;若它是匹配边,标记只可能是左端点过来的,左端点未被标记,右端点也不肯能有标记。

最后注意,不可能存在比|M|更小的了,因为覆盖所有匹配边就需要这么多点。
这样我们就完美证明了König定理和如何构造这个最小覆盖集。

核心代码

void solve() {
    for (int i = 0; i < R; i++) G[i].clear();
    for (int i = 0, x, y; i < N; i++) {
        scanf("%d%d", &x, &y);
        G[--x].push_back(--y);
    }
    memset(match, 0xff, sizeof match);
    memset(cver, 0, sizeof cver);
    int ans = 0;
    for (int i = 0; i < R; i++)
        if (G[i].size()) {
            memset(vis_rgh, 0, sizeof vis_rgh);
            if (dfs(i)) ++ans;
        }
    memset(vis_rgh, 0, sizeof vis_rgh);
    memset(vis_lft, 0, sizeof vis_lft);
    for (int i = 0; i < R; i++)
        if (G[i].size() && !cver[i]) dfs(i);
    printf("%d", ans);
    for (int i = 0; i < R; i++)
        if (G[i].size() && !vis_lft[i]) printf(" r%d", i + 1);
    for (int i = 0; i < C; i++)
        if (vis_rgh[i]) printf(" c%d", i + 1);
    putchar('\n');
}

bool dfs(int u) {
    vis_lft[u] = true;
    for (auto v : G[u])
        if (!vis_rgh[v]) {
            vis_rgh[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return cver[u] = true;
            }
        }
    return false;
}

总结

最小点覆盖和König定理是二分图中比较重要而又难以掌握彻底的知识点。我们用算法解决实际问题的时候,遇到问题不妨再从算法本质去想想,就像这个问题中我们利用寻找增广路的过程来分析如何选择覆盖点一样。最本质的东西不能漏下。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注