题解 P6220 [COCI 2020.3]Skandi

· · 题解

前言

博主很笨 ，如有纰漏，欢迎在评论区指出讨论。

二分图的最大匹配使用 Dinic 算法进行实现，时间复杂度为 O(n\sqrt{e})，其中， n为二分图中左部点的数量， e 为二分图中的边数。若是匈牙利算法，时间复杂度为 O(nm) ， m 为二分图中右部点的数量，不建议使用。

博客园食用更佳

König定理

定理内容：二分图最小点覆盖的点的数量等于二分图最大匹配的边的数量。

构造方法 + 简单证明：

首先求出二分图中的最大匹配，建议使用 Dinic 。

从每一个非匹配点出发，沿着非匹配边正向进行遍历，沿着匹配边反向进行遍历到的点进行标记。选取左部点中没有被标记过的点，右部点中被标记过的点，则这些点可以形成该二分图的最小点覆盖。

遍历代码实现如下：

void dfs(int now) {
    vis[now] = true;
    int SIZ = v[now].size();
    for(int i = 0; i < SIZ; i++) {
        int next = v[now][i].to;
        if(vis[next] || !v[now][i].val)//正向边的容量为0说明是匹配边，反向边的容量为0说明是非匹配边
            continue;
        dfs(next);
    }
}

那么就有以下性质：

有了上述的三条性质，可以发现：按照选取左部点中没有被标记过的点，右部点中被标记过的点的规则，选出来的点的点数必然为最大匹配的边数。左部的非匹配点必然被访问，则必不会被选，右部的非匹配点必不会被访问，则必不会被选。而第三条性质决定了，对于一组匹配点，会选择有且仅有一个点。故而选出的点的点数等于最大匹配的边数。

其次需要解决一个问题：保证这些点覆盖了所有的边。具体可以分为四类：

最后在确保这是最小的方案：反证法，少选一个点，那么至少有一条匹配边会被不选，不满足点覆盖的定义，矛盾。也就是说，至少每一条匹配边都需要选一个点。

如上，证毕。

题目来源：COCI 2019/2020 Contest #6 T4. Skandi

题目大意

给定一个 n\times m 的矩阵，其中的白色点为 0 ， 黑色点为 1 。黑色点可以往下一直扩展到底部，把白色点变成蓝色点，直到遇到黑色点为止。同理，也可向右扩展。问整个矩阵经过最小多少次扩展才能扩展为整个矩阵到不存在白色，并打印出每次扩展是从哪个点开始的，并打印出扩展方向。题目满足第一行第一列一定为黑色点。

思路

一道建模题。

一个白色点变为蓝色点只有两种方法，从它上方或左方的黑色点扩展而来，且只需要一个点扩展即可。可以考虑到最小点覆盖问题。

由于对于一个黑色点来说，它可以往右或往下扩展。那么它就有两个身份，也就是说一个点拥有两个编号。一个编号为把整个矩阵拉成一条链的顺序，另一个编号为前一个编号 +n\times m ，这样不会发生冲突。获得编号的函数：

int GetHash(int i, int j) {
    return (i - 1) * m + j;
}

那么不难发现一个白色点，与其相关的是一个编号 \leqslant n\times m 的点，和一个编号 >n\times m 的点。把这两个点连接起来，就是一张二分图。

问题就转换为找这张图的最小点覆盖问题。使用 Dinic ，在根据上述 König 定理构造即可。

边数为白点的个数，左部点为黑点的个数，则时间复杂度为 O(nm\sqrt{nm}) ，即 O(n^{\frac{3}{2}}m^{\frac{3}{2}}) ，本题的 n ， m 均小于 500 ，大概能够在 1s 内求出答案。

C++代码

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 1e6 + 5;
const int MAXM = 5e2 + 5;
struct Node {
    int to, val, rev;//依次为：下一个点，边的容量，相反的边的编号
    Node() {}
    Node(int T, int V, int R) {
        to = T;
        val = V;
        rev = R;
    }
};
vector<Node> v[MAXN];//用vector存图的癖好...
int dn[MAXN], rt[MAXN];//预处理白色点可以右那两个点扩展而来
queue<int> q;
int de[MAXN], be[MAXN];
int twin[MAXN];
bool vis[MAXN];
int n, m, s, t;
int arr[MAXM][MAXM];
bool bfs() {//将残量网络分层
    bool flag = 0;
    memset(de, 0, sizeof(de));
    while(!q.empty())
        q.pop();
    q.push(s);
    de[s] = 1; be[s] = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        int SIZ = v[now].size();
        for(int i = 0; i < SIZ; i++) {
            int next = v[now][i].to;
            if(v[now][i].val && !de[next]) {
                q.push(next);
                be[next] = 0;
                de[next] = de[now] + 1;
                if(next == t)
                    flag = 1;
            }
        }
    }
    return flag;
}
int dfs(int now, int flow) {//沿着增广路增广
    if(now == t || !flow)
        return flow;
    int i, surp = flow;
    int SIZ = v[now].size();
    for(i = be[now]; i < SIZ && surp; i++) {
        be[now] = i;
        int next = v[now][i].to;
        if(v[now][i].val && de[next] == de[now] + 1) {
            int maxnow = dfs(next, min(surp, v[now][i].val));
            if(!maxnow)
                de[next] = 0;
            v[now][i].val -= maxnow;
            v[next][v[now][i].rev].val += maxnow;
            surp -= maxnow;
        }
    }
    return flow - surp;
}
int Dinic() {//网络最大流，亦可用于二分图匹配
    int res = 0;
    int flow = 0;
    while(bfs())
        while(flow = dfs(s, INF))
            res += flow;
    return res;
}
int GetHash(int i, int j) {//获取点的编号
    return (i - 1) * m + j;
}
void Down(int now, int i, int j) {//黑点向下扩展，每个白点最多遍历到一次
    if(i != now)
        dn[GetHash(now, j)] = GetHash(i, j);
    if(arr[now + 1][j] == 2)
        Down(now + 1, i, j);
} 
void Right(int now, int i, int j) { //黑点向右扩展，每个白点最多遍历到一次
    if(j != now)
        rt[GetHash(i, now)] = GetHash(i, j) + n * m;
    if(arr[i][now + 1] == 2)
        Right(now + 1, i, j);
}
void GetMin(int now) {//dfs求构造方式
    vis[now] = true;
    int SIZ = v[now].size();
    for(int i = 0; i < SIZ; i++) {
        int next = v[now][i].to;
        if(vis[next] || !v[now][i].val)
            continue;
        GetMin(next);
    }
}
int main() {
    scanf("%d %d", &n, &m);
    s = 0; t = 2 * n * m + 1;//源点和汇点初始化
    char ch;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> ch;
            if(ch == '1')
                arr[i][j] = 1;
            else
                arr[i][j] = 2;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i == 1 && j == 1)
                continue;
            if(arr[i][j] == 1) {//向右或向下扩展，一个白点会被访问2次
                Down(i, i, j);
                Right(j, i, j);
            }
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            if(arr[i][j] == 1) {//源点到左部点，汇点到右部点连边
                int now = GetHash(i, j);
                int idnow = v[now].size();
                int ids = v[s].size();
                v[s].push_back(Node(now, 1, idnow));
                v[now].push_back(Node(s, 0, ids));
                now = GetHash(i, j) + n * m;
                idnow = v[now].size();
                int idt = v[t].size();
                v[now].push_back(Node(t, 1, idt));
                v[t].push_back(Node(now, 0, idnow));
            }
        }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(i == 1 && j == 1)
                continue;
            if(arr[i][j] == 1)
                continue;
            int A = dn[GetHash(i, j)];//左部点到右部点连边
            int B = rt[GetHash(i, j)];
            int idA = v[A].size();
            int idB = v[B].size();
            v[A].push_back(Node(B, 1, idB));
            v[B].push_back(Node(A, 0, idA));
        }
    }
    printf("%d\n", Dinic());
    GetMin(s);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(arr[i][j] == 2)
                continue;
            if(!vis[GetHash(i, j)])//打印答案
                printf("%d %d DOLJE\n", i, j);
            if(vis[GetHash(i, j) + n * m])
                printf("%d %d DESNO\n", i, j);
        }
    }
    return 0;
}