精华内容
下载资源
问答
  • 基于深度优先搜索的匹配算法 --- 二分图最大匹配

    一、前言

      图论的算法蕴藏着很多前人的智慧,而且大多数用法很巧妙,匈牙利算法作为相对较为基础的图论算法,是用来求二分图最大匹配问题的。网上对它有很多的解读,比如 Hall 定理、交替路、增广轨,边取反 等等名词,但是这些词汇,对于一个刚接触图论算法的新手来说,是很容易被劝退的,那就违背了我承诺的 让天下没有难学的算法 的 初衷了。所以我经过深思熟虑之后,先不打算郑重其事得介绍这个算法的原理,而是尝试用一些更加口头的术语来解释整个寻找二分图最大匹配的过程。
      当然,我们得先了解下什么是二分图。
      准备好了吗?少年!如果从现在开始努力,那么几年后再回头来看,最差也不过是大器晚成。在这里插入图片描述

    二、二分图

    1、什么是二分图

    • 二分图是两个点集 XXYY 组成的无向图,其中点集 XX 中的点之间互相没有关联,点集 YY中的点之间互相没有关联,但是 点集 XX 和 点集 YY 之间有可能存在关联。我们用边来表示两个点之间的关联,如图二-1-1所示。
      图二-1-1
    • 红色点为 XX 集合中的点,互相之间没有边连接;黄色的点为 YY 集合中的点,互相之间也没有边连接。绿色的直线代表图中的边,用于连接 XX 集合 和 YY 集合中的点。
    • 现实中一个最典型的例子:男人和女人构成的图就是二分图(特殊情况不考虑)。
    • 《天龙八部》中也有一个典型的二分图的例子。
    • 那么,为什么段王爷这么受女人欢迎呢?
      图二-1-2
    • 额…(⊙o⊙)… 这不是我们今天要讨论的话题。

    2、二分图的判定

    1、圈的定义

    • 图论中圈的定义是:任选一个顶点为起点,沿着不重复的边,经过不重复的顶点,之后又回到起点的闭合路径。如图二-2-1所示,(124311 \to 2 \to 4 \to 3 \to 1) 为这个图的一个圈。
      图二-2-1
    • 奇圈就是经过路径的顶点数为奇数的圈,如图二-2-2所示,(1245311 \to 2 \to 4 \to 5 \to 3 \to 1) 为这个图的一个奇圈。
      图二-2-2

    2、二分图判定性质

    • 二分图判定:判断一个图是不是二分图,其实就是判断这个图有没有奇圈。
    • 还是以图二-2-1为例,我们可以把这个图分成两个点集,如图二-2-3所示:
      在这里插入图片描述
    图二-2-3
    • 但是如果存在奇圈,情况就不是这样了,奇圈上的某个点一定既和 XX 点集有关联,又和 YY 点集有关联,如图二-2-4所示:
      在这里插入图片描述
      图二-2-4
    • 可以通过奇偶性来进行证明,相邻两个点的奇偶性一定是不同的,对应到二分图的两个点集中,那么一旦存在奇圈,势必有两个相邻点的奇偶性相同,和二分图的性质产生矛盾。

    3、二分图染色

    • 二分图染色算法的实现是通过判断一个图中是否存在奇圈从而确定它是否是二分图。

    染色算法实现如下:
      1)每次从没有访问过的点中找出一个点作为 当前结点 uu,标记颜色 color[u]=0color[u] = 0
      2)遍历 当前结点 的相邻未访问结点 vv,标记 color[v]=1color[u]color[v] = 1 - color[u],并且设 当前结点vv
      3)重复步骤 1 和 2 直到所有顶点都被染色完毕;

    • 在讲搜索入门的时候,曾经简单介绍过深度优先搜索和广度优先搜索,而在图论算法中,基本都是这两个算法的扩展,后面的章节也会大量用到,那么我们来简单了解下染色算法的 深搜版本 和 广搜版本。

    1)深搜染色

    • dyeDFS()用来对每个结点进行递归染色。具体过程如图二-2-5所示:
      图二-2-5

    实现如下:

    bool BipartiteGraph::dyeDFS(int fat, int u, int c) {
        if (color_[u] != -1) {                             // 1)
            return color_[u] == c;                         // 2)
        }
        color_[u] = c;
        for (int e = head_[u]; ~e; e = edges_[e].next) {   // 3)
            int v = edges_[e].to;
            if (!dyeDFS(u, v, 1 - c)) {                    // 4)
                return false;
            }
        }
        return true;                                      // 5)
    }
    
    • 1)初始化数组 color_[i] = -1;代表所有顶点都还没有被染色;

    • 2)如果染色过程中发现一个结点已经被染色了,并且将要给它染的颜色本身已经染的颜色 不同,则说明产生了冲突(即发现了两个相邻结点染成了相同颜色),则直接返回 false,代表它不是一个二分图;否则,返回true

    • 3)这句话的意思是遍历了所有和结点 uu 相邻的结点,采用的是 链式前向星,是一种边的存储方式,当然也可以采用 邻接矩阵 或者 邻接表,这里就不作多加介绍了,有兴趣的读者可以在我的博客上找到相关的文章进行学习。

    • 4)递归遍历染色的时候发现冲突,则返回 false

    • 5)遍历完所有的点后返回 true,代表这次遍历没有发现冲突;

    • 由于二分图可能是一个非连通图,所以不是只访问一个结点就能遍历到所有结点的,需要对所有结点都进行一次遍历。isBipartite()接口用来真正判断一个完整的图是否是二分图。

    bool BipartiteGraph::isBipartite() {
        memset(color_, -1, sizeof(color_));                 // 1)
        for (int i = 1; i <= vertexcount_; ++i) {
            if (color_[i] == -1 && !dyeDFS(-1, i, 0)) {     // 2)
                return false;
            }
        }
        return true;                                        // 3)
    }
    
    • 1)初始化数组 color_[i] = -1;代表所有顶点都还没有被染色;
    • 2)如果遍历到的结点 ii 尚未被染色,那么将它染色为 0,然后递归枚举它的相邻结点进行染色;如果染色过程中发现冲突(即发现了两个相邻结点染成了相同颜色),则直接返回 false,代表它不是一个二分图。
    • 3)如果所有结点都染色完毕,并且没有发现任何冲突,则函数返回true,代表它是一个二分图。

    2)广搜染色

    • 由于深搜染色可能导致栈溢出,一般可以加上一句话,扩充栈空间:
    #pragma   comment(linker, "/STACK:1024000000,1024000000")
    
    • 当然,也可以将递归改成用栈来实现,或者用广搜去染色,广搜用到的数据结构是队列。具体过程为层层扩展,如图二-2-6所示:
      在这里插入图片描述

      图二-2-6

    • 实现如下:

    bool BipartiteGraph::dyeBFS(int u) {
        queue <int> Q;
        Q.push(u);
        color_[u] = 0;                                      // 1)
        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int e = head_[u]; ~e; e = edges_[e].next) {
                int v = edges_[e].to;
                if (color_[v] == -1) {                     // 2)
                    color_[v] = 1 - color_[u];
                    Q.push(v);
                }
                else if (color_[v] == color_[u]) {         // 3)
                    return false;
                }
            }
        }
        return true;                                       // 4)
    }
    
    • 1)初始化队列里面只有一个结点;
    • 2)对没有染过色的结点,进行交替染色 color_[v] = 1 - color_[u];
    • 3)对染过色的结点,如果两个结点相邻且颜色相同,则返回冲突;
    • 4)所有连通的结点都染色完毕,返回true,代表不存在冲突;
    • 当然,也需要遍历全图,isBipartite()的实现方式和深搜版本一致。

    三、二分图最大匹配

    1、定义

    • 匹配定义:给定一个二分图 GG,在 GG 的一个子图 MM 中,MM 的边集 EE 中的任意两条边都不依附于同一个顶点,则称 MM 是一个匹配。

    • 从匹配的定义可以看出,匹配也是一个图,并且图中的 点数边数 的 2 倍;

    • 还是拿之前的图来举例吧,如图三-1-1所示:

      图三-1-1

    • 红色边组成的 4 个结点、2条边就是这个二分图的一个匹配了;

    • 二分图最大匹配定义:最大匹配就是找到一个子图,满足是匹配,并且边数(点数)最多。

    • 如图三-1-2所示,就是这个二分图的一个最大匹配。但愿有情人终成眷属吧~~
      在这里插入图片描述

      图三-1-2

    2、匈牙利算法

    • 匈牙利算法是用来求二分图最大匹配问题的。网上对它有很多的解读,比如 Hall 定理、交替路、增广轨,边取反 等等名词,但是这些词汇,对于一个刚接触图论算法的新手来说,是很容易被劝退的,那就违背了我承诺的 让天下没有难学的算法 的 初衷了。所以我经过深思熟虑之后,先不打算郑重其事得介绍这个算法的原理,而是尝试先用一些更加口头的术语来解释整个寻找二分图最大匹配的过程。

    • 整个过程是这样的!

    • 1)我们把这件事情想象成一个大型的相亲栏目,里面有男人和女人,作为主办方,我把他们分成两组:XX 组全是男人,YY 组全是女人。
      在这里插入图片描述

      图三-2-1

    • 2)由于这些男人和女人之前在网上已经大致聊过,所以一些男人对一些女人已经产生好感,当然,如果男人 XaX_a 对 女人 YbY_b 有好感,那么 YbY_bXaX_a 也会有好感,因为爱是相互的!你不爱我了,那我也会选择放手!

      图三-2-2

    • 3)作为一个男人!要把握主动权!所以总是男选女!

      图三-2-3

    • 4)每个男人可以选遍所有有好感的女人:如果女人还没有配对,那么恭喜你,直接配对;如果已经配对了,则让之前和这个女人配对的男人再去找其他女人,又转化成了另一个男人找女人的过程,继续递归找;

    • 最终结果有两个:

    • 4.a)由于这个男人的插足,导致最后可能有一个男人被抛弃,这是不道德的行为,所以不能干这种事情!

      图三-2-4

    • 4.b)由于这个男人的插足,导致所有的男女关系都进行了一次轮换,但是匹配的对数多了一对;

      图三-2-5

    • 好了,这就是匈牙利算法的全部内容!

    3、匈牙利算法实现

    • 我们把上面说到的几个步骤再进行一轮回顾。
    • 1)把人分成两组,对应了 二分图
    • 2)互相有好感,对应了 双向图

    匈牙利算法实现如下:
      1)由于二分图是双向图,所以在起初构图的过程一定是建立双向边;
      2)通过染色算法将点集分成两组:color[X]=0color[X]=0color[Y]=1color[Y]=1;
      3)对于每个 color[X]=0color[X]=0 的点 uu,遍历所有和 uu 相邻的点 vv
       3.a)如果 vv 之前没有匹配,则 (u,v)(u, v) 作为一个全新匹配,匹配数加一;
       3.b)否则,让和 vv 之前匹配的点继续递归去找新的匹配,如此反复,直到所有 color[Y]=1color[Y]=1 的点都被访问完毕,还是没有找到,则这次 uu 的匹配作废;如果找到了,(u,v)(u, v) 配对,匹配数加一,并且之前匹配的都进行一次轮换;

    • c++ 代码实现如下:
    int BipartiteGraph::getMaxMatch() {
        dye();                                       // 1)
        int cnt = 0;
        memset(pre_, -1, sizeof(pre_));              // 2)
        for (int i = 1; i <= vertexcount_; ++i) {
            if (color_[i] == 0) {
                memset(visit_, false, sizeof(visit_));
                if (findMatch(i)) {                  // 3)
                    ++cnt;
                }
            }
        }
        return cnt;
    }
    
    • 1)第一步为染色,算法实现上文有完整代码;
    • 2)初始化所有 Y 点集的匹配为 -1, 即不存在;
    • 3)findMatch(i)代表对 ii 进行尝试找匹配,如果找到计数器cnt++,否则没有任何影响;
    • 尝试找匹配的代码实现如下:
    bool BipartiteGraph::findMatch(int u) {
        for (int e = head_[u]; ~e; e = edges_[e].next) {   
            int v = edges_[e].to;
            if (!visit_[v]) {                               // 1)
                visit_[v] = true;
                if (pre_[v] == -1 || findMatch(pre_[v])) {  // 2)
                    pre_[v] = u;                            // 3)
                    return true;
                }
            }
        }
        return false;
    }
    
    • 1)这里用深搜来实现寻找匹配的过程,每个结点在寻找匹配的过程中都要将所有 Y 点集标记为未访问。
    • 2)pre_[v] == -1代表 vv 目前没有任何和它匹配的点;findMatch(pre_[v]) == true;代表 vv 有和它匹配的点,但是那个点能够通过一些办法找到新的匹配;
    • 3)以上这两个条件满足一个,(u,v)(u, v) 就能作为一对新的匹配,更新 pre_[v] = u;
    • 这一步就是网上常说的找增广路的过程。

    四、二分图最大匹配的应用

    • 对于二分图最大匹配来说,更重要的是对一些实质问题的转化,比如通过求解二分图最大匹配,我们可以得到一个二分图的最小顶点覆盖,最小边覆盖,最大独立集、最大完全子图、最小路径覆盖 等等。
    • 在介绍这几个概念之前,我们先来看个引理:

    【引理1】 在最大匹配中,每条匹配边连接的两个顶点 (u,v)(u, v) 最多只有一个与非匹配点有连边。

    • 证明:假设存在一条匹配边连接的两个顶点 (u,v)(u, v),分别存在非匹配边 (u,x)(u, x)(v,y)(v, y),且 xxyy 都是非匹配点,那么可以将 (u,x)(u, x)(v,y)(v, y) 变成匹配边,(u,v)(u, v) 变成非匹配边,从而使得匹配数加一,和最大匹配矛盾,故得证。
    • 如图四-1所示,假设已经找到了最大匹配,并且 (1, 6) 为匹配边,(1, 8) 和 (6, 3) 为非匹配边,其中 3 和 8 为非匹配点,那么可以将 (1, 8) 和 (6, 3) 变成匹配边,(1, 6) 变成非匹配边,从而使得匹配数加一。
      图四-1

      图四-2

    1、最小顶点覆盖

    • 定义:选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
    • 举例:如图四-1-1所示,最小顶点覆盖是 (2,4,6)(2, 4, 6) 三个点组成的点集。
      图四-1-1
    • 结论:二分图最小顶点覆盖 = 二分图最大匹配
    • 证明:对于二分图 GG,以及匹配图 MM,最大匹配数为 mm
    • 1)我们可以构造一个点集,这个点集是从最大匹配 MM 里面取出来的,对于每一条匹配边,选择那个与非匹配点有连边的点(根据引理1,这个点最多只有一个)加入点集 VV;如果不存在,则随便选一个,总共选择 mm 个点。如图四-1-1所示:三条匹配边 (1,6) (2,5) (4,7);点集 VV 构造的时候,(1,6) 这条边选择 6 这个点,(2,5) 这条边选择 2 这个点, (4,7) 这条边选择 4 这个点;这个点集至少可以覆盖 MM,即 最小顶点覆盖 >=m>= m
    • 2)如果 GG 中的边除了 MM 中匹配边以外没有其它非匹配边,那么最小顶点覆盖 =m= m
    • 3)否则,还存在非匹配边,如果这条非匹配边的两个端点都在非匹配点上,那么可以构成一条新的匹配边,从而和最大匹配矛盾;所以这些非匹配边一定是其中一个端点在匹配点上,另一个端点在非匹配点上;
    • 4)令一条非匹配边上的一个端点为 uu ,且 uu 在非匹配点上,那么如果存在一条边 (u,v)(u, v),点 vv 必定是在我们构造出来的点集 VV 中的,于是边 (u,v)(u, v) 一定可以被这个点集覆盖,所以 最小顶点覆盖 =m= m

    【例题1】给定一个 nnn*n 的棋盘,黑白格子组成,白色格子可以放置棋子,黑色格子不能放置棋子,如果一行或者一列上有其它棋子,并且中间没有任何黑色格子,那么这样的放置是非法的,求尽量放置最多的棋子(类似国际象棋中的 “车”)。

    图四-1-2

    • 首先将棋盘进行行分块,分在同一块的一行上只能放一个棋子,如图四-1-3所示:
      图四-1-3
    • 再进行列分块,分在同一块的一列上只能放一个棋子,如图四-1-4所示:
      图四-1-4
    • 那么我们发现,任何一个格子都属于 一个行分块 和 一个列分块,假设一格格子 (r,c)(r,c),它的行分块编号为 xx,列分块编号为 yy,每个能够放置棋子的点一定是要么行分块要么列分块来决定的。那么,我们把每个能够放置棋子的点看成是二分图的边,即建立边 :xyx \to y,选择最少的行列分块(对应于二分图的点)覆盖所有的格子(对应于二分图的边),就相当于把所有的格子上的位置都占据满了。
    • 转换成最小顶点覆盖问题,求构造后的图的二分图最大匹配即可。

    2、最小边覆盖

    • 定义:选了一条边就相当于覆盖了它的两个端点。最小边覆盖就是选择最少的边集,覆盖所有的点集。

    • 举例:如图四-2-1所示,选择的边集为 E = {(2,9), (3, 8), (5, 10), (4, 9), (3, 11)},答案为 5 。

      图四-2-1

    • 结论:二分图的最小边覆盖 = 顶点总数 - 孤立点数 - 二分图最大匹配。

    • 证明:取最少的边,那么一定是优先选择能够一次性覆盖两个点的那种边,即匹配边。假设二分图左边的点数为 X|X| ,右边的点数为 Y|Y|,二分图的最大匹配点数为 M|M|,那么通过匹配边覆盖的点数为 M2|M| * 2,剩下的孤立点有 S|S| 个是不需要被覆盖的,所以还有 X+YM2S|X| + |Y| - |M| * 2 - |S| 个点没有被覆盖,只能通过对应的边数来覆盖。

    • 所以边覆盖的数目为 M+(X+YM2S)=X+YSM|M| + (|X| + |Y| - M * 2 - |S|)= |X| + |Y| - |S| - |M|

    • 如图四-2-1所示,X=6|X| = 6Y=6|Y| = 6M=3|M| = 3S=4|S| = 4,所以最小边覆盖为 6 + 6 - 4 - 3 = 5。

    【例题2】给定一个 nmn*m 的 01 矩阵,每次可以选择 1 x 2 或者 2 x 1 的格子去覆盖 0,且允许重复覆盖,问最少需要选择的格子数。

    • 对于矩阵中任意一个 0,检测四个相邻方向,是否也是 0,如果是,则建立一条边。那么问题就转变成,选择最少的边,覆盖所有点。转化成最小边覆盖问题求解。

    3、最大独立集

    • 定义:选取最多的点,使得图中任意两点都没有关系;

    • 举例:如图四-2-1所示,最大独立集为 V = {1, 3, 5, 7, 8}

      图四-3-1

    • 结论:二分图的最大独立集 = 顶点总数 - 最小顶点覆盖。

    • 证明:这个是非常好理解的,不需要一大堆证明。因为最小顶点覆盖,覆盖了所有的边,所以消去这些顶点,所有的边也就被消去了,从而剩下的点之间两两都不相邻,所以这些剩余点构成了一个点独立集。又由于最小顶点覆盖已经是最少的能够覆盖所有边的点集,不能再少了,所以剩下的点集就是最大的,这就是最大独立集的最直观描述。

      图四-3-2

    【例题3】在学校里,给定一些男孩和女孩的关系图,默认男孩和男孩,女孩和女孩之间都没有关系,求一个最大的集合,使得所有选出来的孩子之间都没有关系。

    • 典型的求最大独立集的问题。求出最大匹配后,用总的点数减去即可。

    4、最大完全子图

    • 定义:选取最多的点,使得图中任意两点都有关系;
    • 结论:二分图的最大团 = 补图的最大独立集。
    • 证明:参考最大独立集,正好是最大独立集相反的情况,所以对原图建立补图,再求最大独立集即可。

    【例题4】nn 个男孩之间都有关系,mm 个女孩之间也都有关系,某些男孩和某些女孩之间有关系,现在需要挑出一些孩子集合,使得所有的孩子都相互有关系,求集合最大值。

    • 这是一个求最大完全子图的问题,如果不是二分图,这将是一个 NP 问题,但是这里是个二分图,我们可以先建立补图,然后问题转换成挑出一些孩子集合,两两之间都没有关系(这时候男孩子和男孩子之间,女孩子和女孩子之间都没有关系了),于是转变成二分图最大独立集问题求解。

    5、有向无环图的最小路径覆盖

    1)不相交的情况

    • 定义:选择一些路径,覆盖所有的点集,且各路径的点集之间不允许有交集,要求路径数最少。

    • 举例:如下图所示,得到的路径为:(1245)(1 \to 2 \to 4 \to 5) (67)(6 \to 7) (3)(3),答案为 3。

    • 说明:由于各路径的点集之间不允许有交集,所以不是 (1245)(1 \to 2 \to 4 \to 5)(3467)(3 \to 4 \to 6 \to 7) ,因为这种方案下 结点4 被用了两次。

    • 结论:有向无环图的最小(不相交)路径覆盖 = 原图结点数 - 拆点后二分图最大匹配数

    • 实现:首先将每个结点 uu 拆成两个结点 ulu_luru_r,如果原图存在边 uvu \to v,则在拆点后的图上建立边:ulvru_l \to v_r。由于原图是有向无环图,所以拆点后的图是一个二分图。如图所示:

    • 对拆点后的图求一次二分图最大匹配,得到:

    • 那么有向无环图的最小(不相交)路径覆盖 = 原图结点数(7) - 拆点后二分图最大匹配数(4)= 3

    • 证明:分成以下几个点去理解就行:

    • 1)初始状态,所有顶点都是一条路径,总共 nn 条路径;

    • 2)每增加一对匹配,对应到原图是连接两个结点,并且这两个结点一定不在同一个连通块(这个在下文进行证明),所以总连通块减一,也就是路径数减一;要使得路径数最少,那么增加的匹配数最大。对应二分图最大匹配。

    • 每增加一对匹配:ulvru_l \to v _r,对应原图加了一条 uvu \to v 的边,假设 uuvv 在同一个连通块内,那么有如下四种情况(橙色边为原本的连接情况,红色边为当前增加匹配后增加的新边):

    • (a)uu 出现大于一条出边,vv出现大于一条入边的情况,和二分图匹配的定义矛盾,这种情况不合法;

    • (b)产生了圈,和有向无环图的前提矛盾,所以这种情况不可能出现;

    • (c)uu 出现大于一条出边的情况,对应到二分图和两个点进行了匹配,和二分图匹配的定义矛盾,这种情况不合法;

    • (d)vv 出现大于一条入边的情况,和二分图匹配的定义矛盾,这种情况不合法;

    • 基于以上四种情况都不合法,所以每增加一条匹配边,在原图中的两个点势必不在一个连通块内,得证。

    2)相交的情况

    • 定义:选择一些路径,覆盖所有的点集,且各路径的点集之间允许有交集,要求路径数最少。

    • 举例:如下图所示,得到的路径为:(1245)(1 \to 2 \to 4 \to 5) (3467)(3 \to 4 \to 6 \to 7),答案为 2。

    • 结论:首先对原图求一次传递闭包得到一个新图,有向无环图的最小(相交)路径覆盖 = 新图结点数 - 拆点后二分图最大匹配数。

    • 证明:因为路径之间是允许相交的,所以对于 2 条路径 abca \to b \to cdbed \to b \to ebb 这个点可以被 2 条路径用,只要建立 aca \to cded \to e 的边,就可以当成求最小不相交路径覆盖的情况来求解了。




    五、二分图最大匹配题集整理

    1、二分图染色和最大匹配

    题目链接 难度 解法
    HDU 1083 Courses ★☆☆☆☆ 最大匹配 模板
    HDU 1179 Ollivanders: Makers of Fine Wands since 382 BC. ★☆☆☆☆ 最大匹配 模板
    HDU 1528 Card Game Cheater ★☆☆☆☆ 最大匹配 模板
    HDU 2063 过山车 ★☆☆☆☆ 最大匹配 模板
    PKU 2584 T-Shirt Gumbo ★☆☆☆☆ 最大匹配 模板
    HDU 2194 Help the vendor and get some M _ ★★☆☆☆ 染色 + 最大匹配
    HDU 4185 Oil Skimming ★★☆☆☆ 染色 + 最大匹配
    HDU 2444 The Accomodation of Students ★★☆☆☆ 染色 + 最大匹配
    HDU 1507 Uncle Tom’s Inherited Land* ★★☆☆☆ 最大匹配 + 路径处理
    HDU 2819 Swap ★★☆☆☆ 最大匹配 + 路径处理
    HDU 2389 Rain on your Parade ★★★☆☆ 最大匹配 + 点集随机
    HDU 3729 I’m Telling the Truth ★★★☆☆ 离散化 + 最大匹配

    2、最小顶点覆盖

    题目链接 难度 解法
    HDU 1054 Strategic Game ★☆☆☆☆ 最小顶点覆盖
    PKU 3041 Asteroids ★★☆☆☆ 最小顶点覆盖
    HDU 2119 Matrix ★★☆☆☆ 最小顶点覆盖
    HDU 1150 Machine Schedule ★★★☆☆ 最小顶点覆盖
    PKU 2226 Muddy Fields ★★★☆☆ 最小顶点覆盖
    HDU 1045 Fire Net ★★★☆☆ 【例题1】最小顶点覆盖
    HDU 1498 50 years, 50 colors ★★★☆☆ 枚举 + 最小顶点覆盖
    HDU 1281 棋盘游戏 ★★★☆☆ 枚举 + 最小顶点覆盖
    HDU 2236 无题II ★★★☆☆ 二分枚举 + 最小顶点覆盖
    HDU 5093 Battle ships ★★★☆☆ 最小顶点覆盖
    HDU 3360 National Treasures ★★★☆☆ 最小顶点覆盖
    HDU 6178 Monkeys ★★★★☆ 树形的匹配问题

    3、最大独立集

    题目链接 难度 解法
    HDU 1068 Girls and Boys ★☆☆☆☆ 【例题3】最大独立集
    HDU 2768 Cat vs. Dog ★★★☆☆ 最大独立集
    HDU 2458 Kindergarten ★★★☆☆ 【例题4】补图的最大独立集

    4、最小边覆盖

    题目链接 难度 解法
    PKU 3020 Antenna Placement ★★☆☆☆ 【例题2】最小边覆盖
    PKU 2724 Purifying Machine ★★★★☆ 最小边覆盖

    5、最小路径覆盖

    题目链接 难度 解法
    HDU 1151 Air Raid ★★☆☆☆ 【例题5】最小(不相交)路径覆盖
    HDU 1350 Taxi Cab Scheme ★★☆☆☆ 最小(可相交)路径覆盖
    HDU 1960 Taxi Cab Scheme ★★☆☆☆ 最小(可相交)路径覆盖
    PKU 2594 Treasure Exploration ★★★☆☆ 最小(可相交)路径覆盖
    PKU 3216 Repairing Company ★★★☆☆ 最小(可相交)路径覆盖
    展开全文
  • 中文正则表达式匹配-正则中文匹配

    万次阅读 多人点赞 2018-05-30 17:13:44
    原文链接:...\w匹配的仅仅是中文,数字,字母,对于国人来讲,仅匹配中文时常会用到,见下匹配中文字符的正则表达式: [\u4e00-\u9fa5]或许你也需要匹配双字节字符,中文也是双...
    原文链接:http://caibaojian.com/zhongwen-regexp.html

    这篇文章主要讲如何使用正则匹配中文字符,中文正则表达式的匹配规则不像其他正则规则一样容易记住,下面一起看看这个中文正则表达式是怎么样的。

    \w匹配的仅仅是中文,数字,字母,对于国人来讲,仅匹配中文时常会用到,见下

    匹配中文字符的正则表达式: [\u4e00-\u9fa5]

    或许你也需要匹配双字节字符,中文也是双字节的字符

    匹配双字节字符(包括汉字在内):[^\x00-\xff]

    注:可以用来计算字符串的长度(一个双字节字符长度计2,ASCII字符计1)

    更多常用正则表达式匹配规则:

    英文字母:[a-zA-Z]
    
    数字:[0-9]

    匹配中文,英文字母和数字及_:

    //code from http://caibaojian.com/zhongwen-regexp.html
    ^[\u4e00-\u9fa5_a-zA-Z0-9]+$

    同时判断输入长度:·

    [\u4e00-\u9fa5_a-zA-Z0-9_]{4,10}
    
    ^[\w\u4E00-\u9FA5\uF900-\uFA2D]*$

    1、一个正则表达式,只含有汉字、数字、字母、下划线不能以下划线开头和结尾:

    ^(?!_)(?!.*?_$)[a-zA-Z0-9_\u4e00-\u9fa5]+$

    其中:

    ^ 与字符串开始的地方匹配

    (?!_)  不能以_开头
    
    (?!.*?_$)  不能以_结尾
    
    [a-zA-Z0-9_\u4e00-\u9fa5]+  至少一个汉字、数字、字母、下划线

    $  与字符串结束的地方匹配

    放在程序里前面加@,否则需要\\进行转义 @"^(?!_)(?!.*?_$)[a-zA-Z0-9_\u4e00-\u9fa5]+$"
    
    (或者:@"^(?!_)\w*(?<!_)$" 或者 @" ^[\u4E00-\u9FA50-9a-zA-Z_]+$ " )

    2、只含有汉字、数字、字母、下划线,下划线位置不限:

    ^[a-zA-Z0-9_\u4e00-\u9fa5]+$

    3、由数字、26个英文字母或者下划线组成的字符串

    ^\w+$

    4、2~4个汉字

    @"^[\u4E00-\u9FA5]{2,4}$";

    5、

    ^[\w-]+(\.[\w-]+)*@[\w-]+(\.[\w-]+)+$

    用:(Abc)+ 来分析: XYZAbcAbcAbcXYZAbcAb


    来源:前端开发博客
    展开全文
  • 正则表达式匹配规则

    万次阅读 2021-01-15 21:42:49
    正则表达式匹配规则限定符:?(0或1次)限定符:* (0或1次或多次)限定符:+ (1次或多次)限定符:{ } (指定次数)使用 () 实现多个字符的匹配或运算符:|[ ] 定义匹配的字符范围元字符 \d \D \w \W \s \S . \b^...


    注:本博客使用到的正则表达式在线测试工具:https://regex101.com/


    • 限定符:?(0或1次)

    ? 表示其前面的一个字符出现的次数可以为0次或1次(可有可无)

    测试示例:oo?
    在这里插入图片描述


    • 限定符:* (0或1次或多次)

    * 表示其前面的一个字符出现的次数可以为0次或1次或多次

    测试示例:om*o
    在这里插入图片描述


    • 限定符:+ (1次或多次)

    + 表示其前面的一个字符出现的次数可以为1次或多次

    测试示例: om+o
    在这里插入图片描述


    • 限定符:{ } (指定次数)

    可以使用 { } 来指定前一个字符出现的次数范围

    {2}表示出现次数为2次

    {2,4}表示出现的次数为2–4次

    {2,}表示出现的次数为2次或2次以上

    测试示例: om{2}o
    在这里插入图片描述
    测试示例: om{2,4}o
    在这里插入图片描述
    测试示例: om{2,}o
    在这里插入图片描述


    • 使用 () 实现多个字符的匹配

    在这里插入图片描述


    • 或运算符:|

    在这里插入图片描述


    • [ ] 定义匹配的字符范围

    [abc]+ 表示匹配字符abc
    在这里插入图片描述
    [0-5] 表示匹配数字0–5
    [K-X] 表示匹配大写字母K–X
    [d-t] 表示匹配小写字母d–t
    在这里插入图片描述
    使用 ^ 反向匹配
    在这里插入图片描述


    • 元字符 \d \D \w \W \s \S . \b

    \d 代表数字字符,相当于 [0-9]
    在这里插入图片描述
    \D 代表非数字字符,相当于 [^0-9]
    在这里插入图片描述

    \w 代表单词字符(数字、字母、下划线)

    \W 代表非单词字符
    在这里插入图片描述
    \s 代表空白符(空格、Tab、换行符)

    \S 代表非空白字符
    在这里插入图片描述

    . 代表除换行符之外的所有字符
    在这里插入图片描述
    \b 代表单词字符的边界(开头或结尾),它只代表位置,不匹配空格、换行和Tab

    在这里插入图片描述


    • ^ 匹配行首, $ 匹配行尾

    ^ 匹配行首
    在这里插入图片描述
    $ 匹配行尾
    在这里插入图片描述


    • 贪婪匹配与懒惰匹配

    示例1:

    贪婪匹配:尽可能匹配多的字符
    在这里插入图片描述
    懒惰匹配:尽可能匹配少的字符
    在这里插入图片描述
    示例2:

    贪婪模式:
    在这里插入图片描述
    懒惰模式:
    在这里插入图片描述


    • 使用实例

    实例1:匹配所有16进制的RGB颜色值:
    在这里插入图片描述

    实例2:IPv4 地址匹配:

    \b((25[0-5]|2[0-4]\d|[01]?\d\d?)\.){3}(25[0-5]|2[0-4]\d|[01]?\d\d?)\b
    

    在这里插入图片描述

    展开全文
  • 史上最全的正则表达式-匹配中英文、字母和数字

    万次阅读 多人点赞 2017-08-29 20:31:28
    在做项目的过程中,使用正则表达式来匹配一段文本中的特定种类字符,是比较常用的一种方式,下面是对常用的正则匹配做了一个归纳整理。 1、匹配中文:[\u4e00-\u9fa5] 2、英文字母:[a-zA-Z] 3、数字:[0-9] 4、匹配...

    在做项目的过程中,使用正则表达式来匹配一段文本中的特定种类字符,是比较常用的一种方式,下面是对常用的正则匹配做了一个归纳整理。

    1、匹配中文:[\u4e00-\u9fa5]

    2、英文字母:[a-zA-Z]

    3、数字:[0-9]

    4、匹配中文,英文字母和数字及下划线:^[\u4e00-\u9fa5_a-zA-Z0-9]+$
    同时判断输入长度:
    [\u4e00-\u9fa5_a-zA-Z0-9_]{4,10}

    5、
    (?!_)  不能以_开头
    (?!.*?_$)  不能以_结尾
    [a-zA-Z0-9_\u4e00-\u9fa5]+  至少一个汉字、数字、字母、下划线
    $  与字符串结束的地方匹配

    6、只含有汉字、数字、字母、下划线,下划线位置不限:
    ^[a-zA-Z0-9_\u4e00-\u9fa5]+$

    7、由数字、26个英文字母或者下划线组成的字符串
    ^\w+$

    8、2~4个汉字
    "^[\u4E00-\u9FA5]{2,4}$";

    9、最长不得超过7个汉字,或14个字节(数字,字母和下划线)正则表达式
    ^[\u4e00-\u9fa5]{1,7}$|^[\dA-Za-z_]{1,14}$
     

    10、匹配双字节字符(包括汉字在内):[^x00-xff]
    评注:可以用来计算字符串的长度(一个双字节字符长度计2,ASCII字符计1)

    11、匹配空白行的正则表达式:ns*r
    评注:可以用来删除空白行

    12、匹配HTML标记的正则表达式:<(S*?)[^>]*>.*?|<.*? />
    评注:网上流传的版本太糟糕,上面这个也仅仅能匹配部分,对于复杂的嵌套标记依旧无能为力

    13、匹配首尾空白字符的正则表达式:^s*|s*$
    评注:可以用来删除行首行尾的空白字符(包括空格、制表符、换页符等等),非常有用的表达式

    14、匹配Email地址的正则表达式:^[a-zA-Z0-9][\w\.-]*[a-zA-Z0-9]@[a-zA-Z0-9][\w\.-]*[a-zA-Z0-9]\.[a-zA-Z][a-zA-Z\.]*[a-zA-Z]$

    评注:表单验证时很实用

    15、手机号:^((13[0-9])|(14[0-9])|(15[0-9])|(17[0-9])|(18[0-9]))\d{8}$

    16、身份证:(^\d{15}$)|(^\d{17}([0-9]|X|x)$)

    17、匹配网址URL的正则表达式:[a-zA-z]+://[^s]*
    评注:网上流传的版本功能很有限,上面这个基本可以满足需求

    18、匹配帐号是否合法(字母开头,允许5-16字节,允许字母数字下划线):^[a-zA-Z][a-zA-Z0-9_]{4,15}$
    评注:表单验证时很实用


    19、匹配国内电话号码:d{3}-d{8}|d{4}-d{7}
    评注:匹配形式如 0511-4405222 或 021-87888822

    20、匹配腾讯QQ号:[1-9][0-9]{4,}
    评注:腾讯QQ号从10000开始

    21、匹配中国邮政编码:[1-9]d{5}(?!d)
    评注:中国邮政编码为6位数字

    22、匹配身份证:d{15}|d{18}
    评注:中国的身份证为15位或18位

    23、匹配ip地址:d+.d+.d+.d+
    评注:提取ip地址时有用


    24、匹配特定数字:
    ^[1-9]d*$    //匹配正整数
    ^-[1-9]d*$   //匹配负整数
    ^-?[1-9]d*$   //匹配整数
    ^[1-9]d*|0$  //匹配非负整数(正整数 + 0)
    ^-[1-9]d*|0$   //匹配非正整数(负整数 + 0)
    ^[1-9]d*.d*|0.d*[1-9]d*$   //匹配正浮点数
    ^-([1-9]d*.d*|0.d*[1-9]d*)$  //匹配负浮点数
    ^-?([1-9]d*.d*|0.d*[1-9]d*|0?.0+|0)$  //匹配浮点数
    ^[1-9]d*.d*|0.d*[1-9]d*|0?.0+|0$   //匹配非负浮点数(正浮点数 + 0)
    ^(-([1-9]d*.d*|0.d*[1-9]d*))|0?.0+|0$  //匹配非正浮点数(负浮点数 + 0)
    评注:处理大量数据时有用,具体应用时注意修正


    25、匹配特定字符串:
    ^[A-Za-z]+$  //匹配由26个英文字母组成的字符串
    ^[A-Z]+$  //匹配由26个英文字母的大写组成的字符串
    ^[a-z]+$  //匹配由26个英文字母的小写组成的字符串
    ^[A-Za-z0-9]+$  //匹配由数字和26个英文字母组成的字符串
    ^w+$  //匹配由数字、26个英文字母或者下划线组成的字符串

    26、
    在使用RegularExpressionValidator验证控件时的验证功能及其验证表达式介绍如下:
    只能输入数字:“^[0-9]*$”
    只能输入n位的数字:“^d{n}$”
    只能输入至少n位数字:“^d{n,}$”
    只能输入m-n位的数字:“^d{m,n}$”
    只能输入零和非零开头的数字:“^(0|[1-9][0-9]*)$”
    只能输入有两位小数的正实数:“^[0-9]+(.[0-9]{2})?$”
    只能输入有1-3位小数的正实数:“^[0-9]+(.[0-9]{1,3})?$”
    只能输入非零的正整数:“^+?[1-9][0-9]*$”
    只能输入非零的负整数:“^-[1-9][0-9]*$”
    只能输入长度为3的字符:“^.{3}$”
    只能输入由26个英文字母组成的字符串:“^[A-Za-z]+$”
    只能输入由26个大写英文字母组成的字符串:“^[A-Z]+$”
    只能输入由26个小写英文字母组成的字符串:“^[a-z]+$”
    只能输入由数字和26个英文字母组成的字符串:“^[A-Za-z0-9]+$”
    只能输入由数字、26个英文字母或者下划线组成的字符串:“^w+$”
    验证用户密码:“^[a-zA-Z]w{5,17}$”正确格式为:以字母开头,长度在6-18之间,
    只能包含字符、数字和下划线。
    验证是否含有^%&',;=?$"等字符:“[^%&',;=?$x22]+”
    只能输入汉字:“^[u4e00-u9fa5],{0,}$”
    验证Email地址:“^w+[-+.]w+)*@w+([-.]w+)*.w+([-.]w+)*$”
    验证InternetURL:“^http://([w-]+.)+[w-]+(/[w-./?%&=]*)?$”
    验证身份证号(15位或18位数字):“^d{15}|d{}18$”
    验证一年的12个月:“^(0?[1-9]|1[0-2])$”正确格式为:“01”-“09”和“1”“12”
    验证一个月的31天:“^((0?[1-9])|((1|2)[0-9])|30|31)$”
    正确格式为:“01”“09”和“1”“31”。
    匹配中文字符的正则表达式: [u4e00-u9fa5]
    匹配双字节字符(包括汉字在内):[^x00-xff]
    匹配空行的正则表达式:n[s| ]*r
    匹配HTML标记的正则表达式:/<(.*)>.*|<(.*) />/
    匹配首尾空格的正则表达式:(^s*)|(s*$)
    匹配Email地址的正则表达式:w+([-+.]w+)*@w+([-.]w+)*.w+([-.]w+)*
    匹配网址URL的正则表达式:http://([w-]+.)+[w-]+(/[w- ./?%&=]*)?

     

    展开全文
  • 正则表达式匹配任意字符

    万次阅读 多人点赞 2016-08-04 14:08:02
    最开始以为.* 可以匹配任意字符,后来发现有问题,匹配不了换行符\n 查了下资料,用[\s\S]*匹配可以  解释:\s空白符,\S非空白符,所以[\s\S]是任意字符
  • 1. re模块的使用过程 #coding=utf-8 # 导入re模块 import re # 使用match方法进行匹配操作 result = re.match(正则表达式,要匹配的字符串) # 如果上一步匹配到数据的话,可以使用group方法来提取数据 result.group()...
  • Java在字符串中查找匹配的子字符串

    万次阅读 多人点赞 2017-05-07 15:25:25
    Java在字符串中查找匹配的子字符串
  • opencv+python实现图像匹配----模板匹配、特征点匹配

    万次阅读 多人点赞 2019-02-12 16:30:46
    文章目录模板匹配与特征匹配python的版本及依赖的库的安装opencv+python模板匹配[^1]匹配材料Template Matchingopencv+python特征匹配[^2]匹配材料BFMatching描述特征点--运行结果不精确基于FLANN的匹配器(FLANN ...
  • 阻抗匹配是什么意思?阻抗匹配原理详解

    万次阅读 多人点赞 2019-06-12 20:00:53
    阻抗匹配是什么意思_阻抗匹配原理详解 -------本文轉載自<http://m.elecfans.com/article/671550.html>  本文主要详解什么是阻抗匹配,首先介绍了输入及输出阻抗是什么,其次介绍了阻抗匹配的原理,最后...
  • 1、正则表达式匹配 ~ 区分大小写匹配 ~* 不区分大小写匹配 !~和!~*分别为区分大小写不匹配及不区分大小写不匹配 ^ 以什么开头的匹配 $ 以什么结尾的匹配 转义字符。可以转. * ?等 * 代表任意字符 2、文件及目录匹配 ...
  • python正则匹配txt特定字符串(有换行)在原txt文件中,我们需要匹配出的字符串为:休闲服务(中间参杂着换行)直接复制到notebook里进行处理完整代码 在原txt文件中,我们需要匹配出的字符串为:休闲服务(中间参杂着...
  • Python:利用原生函数count或正则表达式compile、findall、finditer实现匹配统计(包括模糊匹配的贪婪匹配、懒惰匹配) 目录 利用原生函数count或正则表达式compile、findall、finditer实现匹配统计(包括...
  • opencv模板匹配步骤及Code

    万次阅读 多人点赞 2018-08-20 14:32:01
    opencv模板匹配步骤及Code 首先介绍一下模板匹配的适用场景: 1、图像检索 2、目标跟踪 简单的说,模板匹配最主要的功能就是在一幅图像中去寻找和另一幅模板图像中相似度最高的部分,这就是模板匹配。 比如,...
  • 完美匹配

    千次阅读 2019-05-05 22:40:28
    关于完美匹配的概念问题 自己理解: 1.只要存在完美匹配的图就是完美匹配。可以不用管多余的边 1.首先 满图一定是存在完美匹配。 2.奇数个顶点不能构成完美匹配。因为要满足 组成 完美匹配的那些边 不能有相同的顶点...
  • 中文正则表达式匹配 正则中文匹配

    万次阅读 2019-05-06 10:46:14
    如何使用正则匹配中文字符?中文正则表达式的匹配规则不像其他正则规则一样容易记住,所以小编写了这篇博客,供参考! \w匹配 \w匹配的仅仅是中文,数字,字母,对于国人来讲,仅匹配中文时常会用到,见下 匹配中文...
  • Brute Force匹配(暴力匹配)和FLANN匹配区别
  • 1、前两种都是属于模板匹配的方法,这些概念是在《数字图像处理高级应用》里的,其是移动匹配与向量匹配很像,只是移动匹配对灰度变换的鲁棒性不好。 这里说的移动匹配:就是把模板图像在原图像上进行移动,让后计算...
  • 特征匹配——误匹配剔除

    千次阅读 2018-07-25 21:10:02
    暴力匹配 暴力匹配是指依次查找(穷举搜索)第一组中每个描述符与第二组中哪个描述符最接近。当然初始的暴力匹配得到的误匹配很多。我们可以通过交叉匹配过滤的方法对误匹配进行一定程度的剔除。 这种技术的思想是...
  • 匹配问题

    千次阅读 2018-09-22 15:17:49
    匹配问题匹配问题中的重要概念GS算法GS算法的几个特性 匹配问题中的重要概念 匹配,假设有男人的集合M和女人的集合W,每个男人向女人W求婚,并且两个人成功组成一对,就叫做匹配。 完美匹配,假设集合M和集合W的...
  • 立体匹配

    千次阅读 2019-08-13 10:33:25
    立体匹配是立体视觉研究中的关键部分。其目标是在两个或多个视点中匹配相应像素点,计算视差。通过建立一个能量代价函数,对其最小化来估计像素点的视差,求得深度。 概述 点P和Q,映射到左相机OR像面上的同一点p...
  • 正则表达式 贪婪匹配和懒惰匹配

    万次阅读 2018-08-29 19:40:15
    1、贪婪匹配和懒惰匹配 影响的是正则表达式的限定符的匹配结果;  在限定符后面加上?,则为懒惰模式;在限定符后面不加?,则为贪婪模式;常用的限定符如下: 如下截图参考:...
  • 使用 OpenCV 中的蛮力(Brute-Force)匹配和 FLANN 匹配。 1:Brute-Force 匹配的基础 蛮力匹配器是很简单的。首先在第一幅图像中选取一个关键点然后依次与第二幅图像的每个关键点进行(描述符)距离测试,最后返回距离...
  • NLP之文本匹配及语义匹配应用介绍

    万次阅读 2019-07-11 18:11:57
    2、文本匹配方法概述2-1 传统文本匹配方法2-2 主题模型2-3 深度语义匹配模型表示型交互型3、语义匹配应用介绍3-1 短文本-短文本语义匹配3-2 短文本-长文本语义匹配案例1-用户查询-广告页面相似度案例2:文档关键词...
  • 比较常用的几个正则表达式(匹配数字) 评注:匹配中文还真是个头疼的事,有了这个表达式就好办了 匹配双字节字符(包括汉字在内):[^\x00-\xff] 评注:可以用来计算字符串的长度(一个双字节字符长度计2,ASCII字符...
  • 在前面正则表达式匹配规则里,提到了 .* . :匹配除 "\n" 之外的任何单个字符。要匹配包括 '\n' 在内的任何字符,请使用像 '[.\n]' 的模式 * :匹配0个或多个 使用 .* 的话就可以匹配任意长度的任意字符,但是有...
  • 正则表达式匹配

    千次阅读 2020-09-04 23:36:09
    有道面试题是正则表达式匹配
  • 在Scala的模式匹配中,可以使用类型、通配符、序列、正则表达式,甚至可以深入获取对象的状态。这种对象状态的获取遵循一定的协议,也就是对象内部状态的可见性由该类型的实现来控制,这样我们就可以获取暴露的状态...
  • 简介贪婪匹配先看看整个字符串是否存在匹配,如果未发现匹配,则去掉字符串中的最后一个字符,再次尝试匹配,如果还是未发现匹配再去掉最后一个字符,循环往复直到发现一个匹配或者字符串不剩任何字符串。...
  • 模板匹配,特征点匹配-全

    千次阅读 2019-07-09 23:46:33
    模板匹配:模板匹配是一种最原始、最基本的模式识别方法,研究某一特定对象物的图案位于图像的什么地方,进而识别对象物,这就是一个匹配问题。它是图像处理中最基本、最常用的匹配方法。模板匹配具有自身的局限性,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 432,078
精华内容 172,831
关键字:

匹配