[TYVJ1035]棋盘覆盖 解题报告+匈牙利算法学习

· · 个人记录

题目大意：

给定一张n * n(n<=100)的国际象棋，并告诉你m个被删除的点（即不能再被覆盖的点）。问最多可以使用1 * 2的多米诺骨牌多少块尽可能地覆盖整个棋盘。

分析：

刚拿到时确实没什么思路，尝试了爆搜，写挂了。又试着往dp方向去思考了一下，实在弄不出状态和转移方程。于是只好在我们校内论坛里找了找这题的分类——二分图。说实话，这个东西我也不是很懂，所以还得重新学习。

OIwiki上关于二分图的东西实在是太少了（评论区一楼其实是我），并不能很好地学到一些东西，不过理解下概念还是可以的。

以下为OIwiki中的部分内容：

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。
换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

性质

  • 如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。
  • 二分图不存在长度为奇数的环?
    因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。

就是说二分图是把一张图分成了两部分，每部分内部点性质相同且不互相连接。二分图的每条边都连着性质不同的两个点，因此不存在奇数环（通过上图就能很好理解）。

（这篇二分图详解可以先用来学习基本概念）

那么，二分图对这题有什么用呢？

我也不知道！不会啊！为什么要写这题QAQ

网上题解大部分为二分图的最大匹配（代码看上去都比较类似）与最大流(再见)，因此先学习一下二分图的最大匹配说不定就有思路了。

这些概念理解起来还不算难。继续吧。

交替路：从一个为匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径。

增广路：当一条交替路连接了两个未匹配点时，这条交替路就是一条增广路。(与增广矩阵无瓜)

  • 增广路的性质一：长度len是奇数。(来源《算法竞赛进阶指南》)

  • 性质二：增广路径上奇数编号的边为非匹配边，偶数边为匹配边。(来源同上)

  • 性质三：由一、二可得，增广路上的非匹配边总比匹配边数多一。

这些概念理解起来也还不算难。继续吧。

匈牙利算法：

又名增广路算法。基本思想是找出最长的增广路，然后这就是二分图的最大匹配（？？大雾弥漫+黑人问号脸.jpg）。步骤如下：（摘录自：《算法竞赛进阶指南》第0x68节）

  1. 设S为空集，即所有边都是非匹配边。
  2. 寻找增广路path，把路径上所有的边的匹配状态取反，得到一个更大的匹配S'。
  3. 重复第2步，直到图中不存在增广路。

    该算法的关键在于如何找到一条增广路。匈牙利算法是遍历二分图左部所有节点并为它们依次寻找一个匹配的右部节点。
    比如为了给某左部节点x寻找一个匹配的右部节点y，为了能让它们匹配，y需要满足以下两个条件之一：

    • y本身就是非匹配点。
    • y已经与左部另一节点x'匹配，但从x'出发仍能找到另一右部节点y'与之匹配。

（看看这熟悉的操作！如果还不熟，这篇博客是一定要看的——趣写算法系列之--匈牙利算法。）

至于匈牙利算法的正确性，基于的是贪心策略。它的一个重要特点是：当一个节点成为匹配点后，至多因为找到增广路而更换匹配对象，但绝不会再变回非匹配点。

前置知识已经差不多搞定了。下面就可以开始搞这题啦！

所以这题为什么可以用这个二分图的最大匹配做啊？

好吧我还是比较迷茫。

于是我再次打开了《算法竞赛进阶指南》。对于这题，有一些前置内容，不必深究。但书上对这题的解读却是相当的好啊：

首先看二分图匹配的模型的两个要素：

  • 节点能分成独立的两个集合，每个集合内部有0条边。
  • 每个节点只能与一条匹配边相连。(不记得了就往上翻去不是我)
    那我们把它简称为 “0要素” 和 “1要素” 。分析题目时就要注意寻找具有这种“0”和“1”性质的对象，从而fa发现突破口。（原话照抄）

本题中，任意两张骨牌都不能重叠，也就是每个格子至多被一张骨牌覆盖。而骨牌的大小为1 * 2，覆盖两个相邻的格子。这与恰好与“1要素”对应。于是我们可以把棋盘上没有被禁的格子作为节点，把骨牌作为无向边（两个相邻的格子对应的节点连边），建立二分图。

\color{grey}\text{原来如此！似乎有点理解了。}

如果把行号加列号为偶数的格子染成白色，行号加列号为奇数的格子染成黑色，那么两个相同颜色的格子不可能被同一骨牌覆盖，也就是同色格子之间没有边相连，这恰好与“0要素”对应。于是，怎么做就很显然了。使用匈牙利算法，白色格子做左部节点，黑色格子做右部节点。题目想要尽可能多地放置骨牌，因此这就是二分图的最大匹配了。

\color{grey}\text{似乎有点豁然开朗的感觉了。}

既然思路已经明朗，那就直接上代码吧!

#pragma GCC optimize(2)//没用的东西
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10086,M = N*4;//N开到n*n的范围，M则为N*4（四个方向）
int cxk[4]={1,0,0,-1},qbl[4]={0,1,-1,0};//方向数组
int n,m,tot,match[N];//match记录连接情况
int nxt[M],ver[M],head[N];//邻接表存图
bool p[105][105],used[N];//p记录被禁的点，used用于枚举各左部点时标记

inline int qread(){//快读
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*w;
}

inline void add(int x,int y){//邻接表存图
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}

inline bool dfs(int x){//匈牙利算法板子
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(!used[y]){
            used[y]=true;
            if(!match[y]||dfs(match[y])){
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    n=qread(),m=qread();
    for(int i=1;i<=m;++i){
        int x=qread(),y=qread();
        p[x][y]=true;//记录被禁放的点
    }
    for(int i=1;i<=n;++i)//枚举棋盘各点
        for(int j=1;j<=n;++j)
            if(!p[i][j]){//如果可以用
                int num=(i-1)*n+j;//为了方便处理将二维转成一维，重新编号
                for(int k=0;k<4;++k){
                    int x=i+cxk[k],y=j+qbl[k];//四个方向上相邻的点
                    if(x>=1&&x<=n&&y>=1&&y<=n&&!p[x][y]&&(x+y)%2)//如果在棋盘范围内，没有被禁止，且点行列数和为奇数
                        add(num,(x-1)*n+y);//加边
                }
            }
    int ans=0;
    for(int i=1;i<=n*n;++i){//因为每个点都按一维处理，因此从1扫到n*n
        memset(used,false,sizeof(used));//每次找都要清空一次标记数组
        if(dfs(i))ans++;//如果左右匹配成功边数+1
    }printf("%d\n",ans);
    return 0;
}
FIN