精华内容
下载资源
问答
  • 匈牙利算法 二分图匹配 matlab代码 最近学习了一下匈牙利算法,写了个拙劣的代码,噗 希望可以和大噶交流~ 程序是基于增广路径方法的递归结构 算法流程图 代码 %% % % % % % % % % % % % % % % % % % % % % % % %...

    匈牙利算法 二分图匹配 matlab代码

    最近学习了一下匈牙利算法,写了个拙劣的代码,噗
    希望可以和大噶交流~
    程序是基于增广路径方法的递归结构

    1. 算法流程图
      学了好几年编程 第一次画流程图·······
    2. 代码
    %% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % 
    % % % % % % % % % % % % % % % % 信息说明 % % % % % % % % % % % % % % % % % %
    % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
    %% 程序说明
    %{
    Author:暮烟暮烟
    Date:2020.11.11
    
    匈牙利算法找到二分图G=(V,E)的最大匹配M
    V=X+Y,X有n个顶点,Y包含m个顶点
    仅在主程序中可以更新M和num_M
    子程序仅仅得到增广路径
    %}
    %% 输入变量说明
    %{
    效率矩阵C=n*m=[0 1 0 1 1 0;
                  1 1 0 0 0 0;
                  0 1 0 0 0 1;
                  0 0 0 1 1 0;
                  0 1 1 0 0 0;]
    %}
    %% 输出变量说明
    %{
    M:图G的最大匹配M(实际应用中一般也是完美匹配)
    num_M:最大匹配数
    %}
    %% 关键变量说明
    %{
    X:X顶点匹配标识向量
    *_X:X中顶点的位置下标
    Y:Y顶点匹配标识向量
    *_Y:Y中顶点的位置下标
    P:M-增广路径
    %}
    %% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
    % % % % % % % % % % % % % % %% % 主程序代码部分 % % % % % % % % % % % % % % %
    % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
    %% 主程序
    % ===============================初始化参数=================================
    clear all;
    C = [0 1 0 1 1 0;
         1 1 0 0 0 0;
         0 1 0 0 0 1;
         0 0 0 1 1 0;
         0 1 1 0 0 0;];
    [n,m] = size(C);
    M = zeros(n,m);
    X = zeros(1,n);
    Y = zeros(1,m);
    num_M = 0; %最大匹配数
    
    
    % ==================================遍历Xi=================================
    for i_X=1:n
        P = zeros(n,m); %清空增广路径
        
        %===============================遍历Yj=================================   
        for j_Y=1:m
    
            %------------------Yj和Xi是连接点 且 Yj未匹配------------------------
            if (C(i_X,j_Y))&&(~max(M(:,j_Y)))
                %找到新匹配Xi-Yj 有增广路径 最大匹配+1
                P(i_X,j_Y) = 1;
                X(i_X) = 1;
                Y(j_Y) = 1;
                M = xor(M,P);
                num_M = num_M+1;
               
            %-----------------Yj和Xi是连接点 且 Yj已经匹配-----------------------
            elseif (C(i_X,j_Y))&&(max(M(:,j_Y)))
                u_X = find(M(:,j_Y));%找到与Yj匹配的顶点Xu
                
                %----------------Xu是否可以和其它顶点匹配------------------------
                [P,X,Y] = DfsFun(u_X,j_Y,X,Y,C,M,P);
    
                if ~Y(j_Y)
                %Xn可以和其它顶点匹配 释放Yj
                %找到新匹配Xi-Yj 有增广路径 最大匹配+1
                    P(i_X,j_Y) = 1;
                    X(i_X) = 1;
                    Y(j_Y) = 1;
                    M = xor(M,P);%异或得到新M
                    num_M = num_M+1;
                end%Xu不可以和其它点匹配 进入下一个Y的循环
                
            end %Yj和Xi不是连接点 进入下一个Y的循环
            
            %-----------------------Xi找到匹配 跳出循环--------------------------
            if X(i_X)
                break;
            end
        end
    end
    
    
    %=====================输出最大匹配M和最大匹配数num_M=========================
    M
    num_M
    
    
    %% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
    % % % % % % % % % % % % % % % % 局部函数代码部分 % % % % % % % % % % % %% % %
    % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % %
    %% 局部函数DfsFun
    function [P,X,Y] = DfsFun(u_X,j_Y,X,Y,C,M,P)
    %Xu是否能找到Yj以外的匹配
    %Y(j_Y)表示 0代表找到 1代表未找到
    
    %==================================参数初始化===============================
    [n,m] = size(M);
    % P = zeros(n,m);
    P(u_X,j_Y) = 1;
    
    %=================================遍历Yj以外的Y=============================
    %----------------------------------确定v_Y取值------------------------------
    if j_Y==1
        v_Y = 2:m;
    elseif j_Y==m
        v_Y = 1:m-1;
    else
        v_Y = [1:j_Y-1,j_Y+1:m];
    end
    
    for v_Y=v_Y
        
        %-----------------------Yv是Xu的连接点 且Yv未匹配------------------------
        if (C(u_X,v_Y))&(~M(:,v_Y))
            %找到新匹配 原本的Yj-Xu  换为Xu-Yv和Yj-Xi 
            Y(v_Y) = 1;
            Y(j_Y) = 0;%释放Yj
            P(u_X,v_Y) = 1;
            
        %----------------------Yv是Xu的连接点 且Yv已经匹配Xk---------------------
        elseif (C(u_X,v_Y))&&(max(M(:,v_Y)))
                k_X = find(M(:,v_Y));%找到与Yv匹配的顶点Xk
                
                %----------------Xk是否可以和其它顶点匹配------------------------
                [P,X,Y] = DfsFun(k_X,v_Y,X,Y,C,M,P);
                %Xk可以和其它顶点匹配
                if Y(v_Y)==0 %释放Yv
                    Y(v_Y) = 1;
                    Y(j_Y) = 0;
                    P(u_X,v_Y) = 1;
                end %Xk不可以和其它点匹配 进入下一个Y的循环
        end %Yv和Xu不是连接点 进入下一个Y的循环
            
        %------------------------Xu找到Yj以外的匹配 跳出循环---------------------
        if ~Y(j_Y)
             break;
        end
    end
    end
    

    希望大家多多交流提意见啊,喵

    展开全文
  • 基于聚类和二分图匹配的物流派件调度方法.pdf
  • 若任何一个最大匹配方案的匹配边都包括 (x,y),(x,y),(x,y), 则称 (x,y)(x,y)(x,y) 为二分图匹配的必须边 ... 若 (x,y)(x,y)(x,y) 至少属于一个最大匹配的方案 ,,, 则称 (x,y)(x,y)(x,y) 为二分图匹配的可行边 ... ...

    定义

    给定一张二分图 , , , 其最大匹配方案不一定是唯一的 . . . 若任何一个最大匹配方案的匹配边都包括 ( x , y ) , (x,y), (x,y), 则称 ( x , y ) (x,y) (x,y) 为二分图匹配的必须边 . . . ( x , y ) (x,y) (x,y) 至少属于一个最大匹配的方案 , , , 则称 ( x , y ) (x,y) (x,y) 为二分图匹配的可行边 . . .

    解法

    保证完备匹配时

    我们先求出任意一组完备匹配的方案 , , , 此时所有节点都是匹配点 . . .

    根据定义 , , , ( x , y ) (x,y) (x,y) 是必须边 , , , 当且仅当以下两个条件满足 : : :

    1. ( x , y ) (x,y) (x,y) 当前是匹配边 . . .
    2. 删除边 ( x , y ) (x,y) (x,y) , , , 不能找到另一条从 x x x y y y 的增广路 . . .

    ( x , y ) (x,y) (x,y) 是可行边 , , , 当且仅当满足以下两个条件之一 : : :

    1. ( x , y ) (x,y) (x,y) 当前是匹配边 . . .

    2. ( x , y ) (x,y) (x,y) 是非匹配边 , , , 设当前 x x x u u u 匹配 , , , y y y v v v 匹配 , , , 连接边 ( x , y ) (x,y) (x,y) , , , 节点 u , v u,v u,v 失去匹配 . . .

      必须找到一条从 u u u v v v 的增广路 , , , 来保证最大匹配不变 . . .

    如果我们把二分图 G G G 中的 " " " 非匹配边 " " " 看作从左部到右部的有向边 , , , 把二分图 G G G 中的 " " " 匹配边 " " " 看作从右部到左部的有向边 , , , 构成一张新的有向图 , , , 记为 G ′ , G', G, 那么 G G G 中从 x x x y y y 有增广路 , , , 等价于 G ′ G' G 中存在从 x x x y y y 的路径 . . .

    考虑必须边的条件 , , , ( x , y ) (x,y) (x,y) 是匹配边 , , , 对应 G ′ G' G 中有一条从 y y y x x x 的有向边 . . . 在此条件下 , , , x x x y y y 之间还存在一条路径 , , , x x x y y y 处于同一个强连通分量中 . . .

    因此 , , , 必须边的判定条件是 : : : ( x , y ) (x,y) (x,y) 当前是二分图 G G G 的匹配边 , , , 并且 x , y x,y x,y 两点在有向图 G ′ G' G 中属于不同的 S c c . Scc. Scc.

    类似 , , , 可行边的判定条件是 : : : ( x , y ) (x,y) (x,y) 当前是二分图 G G G 的匹配边 , , , 或者 x , y x,y x,y 两点在有向图 G ′ G' G 中属于相同的 S c c . Scc. Scc.

    综上 , , , 非必须可行边的判定条件是 , , , x , y x,y x,y 两点在有向图 G ′ G' G 中属于相同的 S c c . Scc. Scc.

    不保证完备匹配时

    在这种情况下 , , , 必须边 , , , 可行边的第二个条件会出现问题 . . . ( x , y ) (x,y) (x,y) 是非匹配边 : : :

    1. x , y x,y x,y 二者之一可能本来就是非匹配点 . . . 不妨设 y y y 是非匹配点 , , , 此时直接断开 x x x 原来的匹配边 , , , 连接 ( x , y ) , (x,y), (x,y), 得到的匹配集仍然是最大匹配 . . .
    2. 即使当前 x x x u u u 匹配 , , , y y y v v v 匹配 , , , 连接边 ( x , y ) (x,y) (x,y) , , , 节点 u , v u,v u,v 失去匹配 , , , 我们也不一定要找到从 u u u v v v 的增广路 , , , 如果从 u u u 出发找到另一个非匹配点 z z z 的增广路 , , , 同样可以得到一组包含 ( x , y ) (x,y) (x,y) 的最大匹配 . . .

    所以我们不能像完备匹配中一样 , , , 直接用强连通分量进行判定 . . . 然而 , , , 我们可以借助网络流中的源点和汇点 . . .

    z z z 是当前非匹配点 , , , ( z , T ) (z,T) (z,T) 的剩余容量必定为 1. 1. 1. v v v 当前是匹配点 , , , ( v , T ) (v,T) (v,T) 的剩余容量必定为 0 , 0, 0, ( T , v ) (T,v) (T,v) 的剩余容量必定为 1. 1. 1. 换言之 , , , 残量网络中存在路径 ( ⋯ → z → T → v ⋯   ) . (\cdots \rightarrow z\rightarrow T\rightarrow v\cdots). (zTv). 若二分图中 u u u z z z 有增广路 , , , 则残量网络上 u u u 能到达 z , z, z, 进而到达 v , v, v, ( u , v ) (u,v) (u,v) 通过汇点 T T T 仍在同一个强连通分量中 . . .

    因此 , , , 必须边的判定条件是 : : : ( x , y ) (x,y) (x,y) 流量为 1 ( 1( 1( 不是残量网络 ) ) ) , , , 并且 x , y x,y x,y 两点在残量网络中属于不同的 S c c . Scc. Scc.

    类似 , , , 可行边的判定条件是 : : : ( x , y ) (x,y) (x,y) 流量为 1 1 1 , , , 或者 x , y x,y x,y 两点在残量网络中属于相同的 S c c . Scc. Scc.

    展开全文
  • 算法讲解:二分图匹配【图论】

    万次阅读 多人点赞 2018-07-23 09:46:34
    二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所...

    二分图匹配,自然要先从定义入手,那么二分图是什么呢?

    二分图:

    二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

    简单的说,一个图被分成了两部分,相同的部分没有边,那这个图就是二分图,二分图是特殊的图。

    匹配:

    给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。
    极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。
    如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
    求二分图匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

    注意匈牙利算法,除了二分图多重匹配外在二分图匹配中都可以使用。

    注:二分图匹配中还有一个hk算法,复杂度为o(sqrt(n)*e)由于复杂度降低较低,代码量飙升而且绝大多数情况下没人会闲的卡个sqrt的复杂度。。在此先不讲了,有兴趣可以自己百度,貌似卡这个算法的只有hdu2389

    嘛 首先我们讲解一下匈牙利算法的过程:

    匈牙利算法:

    匈牙利算法几乎是二分图匹配的核心算法,除了二分图多重匹配外均可使用

    匈牙利算法实际上就是一种网络流的思想,其核心就是寻找增广路。具体操作就是嗯。。拉郎配

     

    注:以下转自 http://blog.csdn.net/dark_scope/article/details/8880547

    匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

    -------等等,看得头大?那么请看下面的版本:

     

    通过数代人的努力,你终于赶上了剩男剩女的大潮,假设你是一位光荣的新世纪媒人,在你的手上有N个剩男,M个剩女,每个人都可能对多名异性有好感(惊讶-_-||暂时不考虑特殊的性取向),如果一对男女互有好感,那么你就可以把这一对撮合在一起,现在让我们无视掉所有的单相思(好忧伤的感觉快哭了),你拥有的大概就是下面这样一张关系图,每一条连线都表示互有好感。

     

    本着救人一命,胜造七级浮屠的原则,你想要尽可能地撮合更多的情侣,匈牙利算法的工作模式会教你这样做:

    ===============================================================================

    一: 先试着给1号男生找妹子,发现第一个和他相连的1号女生还名花无主,got it,连上一条蓝线

     

    ===============================================================================

    :接着给2号男生找妹子,发现第一个和他相连的2号女生名花无主,got it

     

    ===============================================================================

    :接下来是3号男生,很遗憾1号女生已经有主了,怎么办呢?

    我们试着给之前1号女生匹配的男生(也就是1号男生)另外分配一个妹子。

     

    (黄色表示这条边被临时拆掉)

     

    与1号男生相连的第二个女生是2号女生,但是2号女生也有主了,怎么办呢?我们再试着给2号女生的原配(发火发火)重新找个妹子(注意这个步骤和上面是一样的,这是一个递归的过程)

     

     

    此时发现2号男生还能找到3号女生,那么之前的问题迎刃而解了,回溯回去

     

    2号男生可以找3号妹子~~~                  1号男生可以找2号妹子了~~~                3号男生可以找1号妹子

    所以第三步最后的结果就是:

     

    ===============================================================================

    : 接下来是4号男生,很遗憾,按照第三步的节奏我们没法给4号男生腾出来一个妹子,我们实在是无能为力了……香吉士同学走好。

     

    ===============================================================================

    这就是匈牙利算法的流程,其中找妹子是个递归的过程,最最关键的字就是“腾”字

    其原则大概是:有机会上,没机会创造机会也要上

     

     hdu2063:

    hdu2063就是一道裸二分图最大匹配的问题,直接上匈牙利算法即可。

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<queue>
    #include<vector>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N=505;
    int line[N][N];
    int girl[N],used[N];
    int k,m,n;
    bool found(int x)
    {
        for(int i=1; i<=n; i++)
        {
            if(line[x][i]&&!used[i])
            {
                used[i]=1;
                if(girl[i]==0||found(girl[i]))
                {
                    girl[i]=x;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int x,y;
        while(scanf("%d",&k)&&k)
        {
            scanf("%d %d",&m,&n);
            memset(line,0,sizeof(line));
            memset(girl,0,sizeof(girl));
            for(int i=0; i<k; i++)
            {
                scanf("%d %d",&x,&y);
                line[x][y]=1;
            }
            int sum=0;
            for(int i=1; i<=m; i++)
            {
                memset(used,0,sizeof(used));
                if(found(i)) sum++;
            }
            printf("%d\n",sum);
        }
        return 0;
    }
    

    二分图最优匹配:

    接下来就是二分图最优匹配的km算法了

    km算法理解起来着实很困难,我其实只能照着代码讲,不然根本讲不明白。不过听一个学长说要理解思想而不是代码。。。那就试着空讲一下吧。

    一般对KM算法的描述,基本上可以概括成以下几个步骤: 
    (1) 初始化可行标杆 
    (2) 用匈牙利算法寻找完备匹配 
    (3) 若未找到完备匹配则修改可行标杆 
    (4) 重复(2)(3)直到找到相等子图的完备匹配 

    关于该算法的流程及实施,网上有很多介绍,基本上都是围绕可行标杆如何修改而进行的讨论,至于原理并没有给出深入的探讨。 

    KM算法是用于寻找带权二分图最佳匹配的算法。 

    二分图是这样一种图:所有顶点可以分成两个集:X和Y,其中X和Y中的任意两个在同一个集中的点都不相连,而来自X集的顶点与来自Y集的顶点有连线。当这些连线被赋于一定的权重时,这样的二分图便是带权二分图。 

    二分图匹配是指求出一组边,其中的顶点分别在两个集合中,且任意两条边都没有相同的顶点,这组边叫做二分图的匹配,而所能得到的最大的边的个数,叫做二分图的最大匹配。 

    我们也可以换个角度看二分图的最大匹配,即二分图的每条边的默认权重为1,我们求到的二分图的最大匹配的权重最大。对于带权二分图,其边有大于0的权重,找到一组匹配,使其权重最大,即为带权二分图的最佳匹配。 

    匈牙利算法一般用于寻找二分图的最大匹配。算法根据一定的规则选择二分图的边加入匹配子图中,其基本模式为: 

    初始化匹配子图为空 
    While 找得到增广路径 
    Do 把增广路径添加到匹配子图中 

    增广路径有如下特性: 
    1. 有奇数条边 
    2. 起点在二分图的X边,终点在二分图的Y边 
    3. 路径上的点一定是一个在X边,一个在Y边,交错出现。 
    4. 整条路径上没有重复的点 
    5. 起点和终点都是目前还没有配对的点,其他的点都已经出现在匹配子图中 
    6. 路径上的所有第奇数条边都是目前还没有进入目前的匹配子图的边,而所有第偶数条边都已经进入目前的匹配子图。奇数边比偶数边多一条边 
    7. 于是当我们把所有第奇数条边都加到匹配子图并把条偶数条边都删除,匹配数增加了1. 

    例如下图,蓝色的是当前的匹配子图,目前只有边x0y0,然后通过x1找到了增广路径:x1y0->y0x0->x0y2 

     

    其中第奇数第边x1y0和x0y2不在当前的匹配子图中,而第偶数条边x0y0在匹配子图中,通过添加x1y0和x0y2到匹配子图并删除x0y0,使得匹配数由1增加到了2。每找到一条增广路径,通过添加删除边,我们总是能使匹配数加1. 

    增广路径有两种寻径方法,一个是深搜,一个是宽搜。例如从x2出发寻找增广路径,如果是深搜,x2找到y0匹配,但发现y0已经被x1匹配了,于是就深入到x1,去为x1找新的匹配节点,结果发现x1没有其他的匹配节点,于是匹配失败,x2接着找y1,发现y1可以匹配,于是就找到了新的增广路径。如果是宽搜,x1找到y0节点的时候,由于不能马上得到一个合法的匹配,于是将它做为候选项放入队列中,并接着找y1,由于y1已经匹配,于是匹配成功返回了。相对来说,深搜要容易理解些,其栈可以由递归过程来维护,而宽搜则需要自己维护一个队列,并对一路过来的路线自己做标记,实现起来比较麻烦。 

    对于带权重的二分图来说,我们可以把它看成一个所有X集合的顶点到所有Y集合的顶点均有边的二分图(把原来没有的边添加入二分图,权重为0即可),也就是说它必定存在完备匹配(即其匹配数为min(|X|,|Y|))。为了使权重达到最大,我们实际上是通过贪心算法来选边,形成一个新的二分图(我们下面叫它二分子图好了),并在该二分图的基础上寻找最大匹配,当该最大匹配为完备匹配时,我们可以确定该匹配为最佳匹配。(在这里我们如此定义最大匹配:匹配边数最多的匹配和最佳匹配:匹配边的权重和最大的匹配。) 

    贪心算法总是将最优的边优先加入二分子图,该最优的边将对当前的匹配子图带来最大的贡献,贡献的衡量是通过标杆来实现的。下面我们将通过一个实例来解释这个过程。 

    有带权二分图: 

     
    算法把权重转换成标杆,X集跟Y集的每个顶点各有一个标杆值,初始情况下权重全部放在X集上。由于每个顶点都将至少会有一个匹配点,贪心算法必然优先选择该顶点上权重最大的边(最理想的情况下,这些边正好没有交点,于是我们自然得到了最佳匹配)。最初的二分子图为:(可以看到初始化时X标杆为该顶点上的最大权重,而Y标杆为0) 

     
    从X0找增广路径,找到X0Y4;从X1找不到增广路径,也就是说,必须往二分子图里边添加新的边,使得X1能找到它的匹配,同时使权重总和添加最大。由于X1通往Y4而Y4已经被X0匹配,所以有两种可能,一个是为X0找一个新的匹配点并把Y4让给X1,或者是为X1找一个新的匹配点,现在我们将要看到标杆的作用了。根据传统的算法描述,能够进入二分子图的边的条件为L(x)+L(y)>=weight(xy)。当找不到增广路径时,对于搜索过的路径上的XY点,设该路径上的X顶点集为S,Y顶点集为T,对所有在S中的点xi及不在T中的点yj,计算d=min{(L(xi)+L(yj)-weight(xiyj))},从S集中的X标杆中减去d,并将其加入到T集中的Y的标杆中,由于S集中的X标杆减少了,而不在T中的Y标杆不变,相当于这两个集合中的L(x)+L(y)变小了,也就是,有新的边可以加入二分子图了。从贪心选边的角度看,我们可以为X0选择新的边而抛弃原先的二分子图中的匹配边,也可以为X1选择新的边而抛弃原先的二分子图中的匹配边,因为我们不能同时选择X0Y4和X1Y4,因为这是一个不合法匹配,这个时候,d=min{(L(xi)+L(yj)-weight(xiyj))}的意义就在于,我们选择一条新的边,这条边将被加入匹配子图中使得匹配合法,选择这条边形成的匹配子图,将比原先的匹配子图加上这条非法边组成的非法匹配子图的权重和(如果它是合法的,它将是最大的)小最少,即权重最大了。好绕口的。用数学的方式表达,设原先的不合法匹配(它的权重最大,因为我们总是从权重最大的边找起的)的权重为W,新的合法匹配为W’,d为min{W-W’i}。在这个例子中,S={X0, X1},Y={Y4},求出最小值d=L(X1)+L(Y0)-weight(X1Y0)=2,得到新的二分子图: 

     
    重新为X1寻找增广路径,找到X1Y0,可以看到新的匹配子图的权重为9+6=15,比原先的不合法的匹配的权重9+8=17正好少d=2。 
    接下来从X2出发找不到增广路径,其走过的路径如蓝色的路线所示。形成的非法匹配子图:X0Y4,X1Y0及X2Y0的权重和为22。在这条路径上,只要为S={X0,X1,X2}中的任意一个顶点找到新的匹配,就可以解决这个问题,于是又开始求d。 
    d=L(X0)+L(Y2)-weight(X0Y2)=L(X2)+L(Y1)-weight(X2Y1)=1. 
    新的二分子图为: 

     

    重新为X2寻找增广路径,如果我们使用的是深搜,会得到路径:X2Y0->Y0X1->X1Y4->Y4X0->X0Y2,即奇数条边而删除偶数条边,新的匹配子图中由这几个顶点得到的新的权重为21;如果使用的是宽搜,会得到路径X2Y1,另上原先的两条匹配边,权重为21。假设我们使用的是宽搜,得到的新的匹配子图为: 

     
    接下来依次类推,直到为X4找到一个匹配点。 

    KM算法的最大特点在于利用标杆和权重来生成一个二分子图,在该二分子图上面找最大匹配,而且,当些仅当找到完备匹配,才能得到最佳匹配。标杆和权重的作用在于限制新边的加入,使得加入的新边总是能为子图添加匹配数,同时又令权重和得到最大的提高。

     

    二分图多重匹配:

    设源点汇点直接网络流即可,在此不细讲,会在网络流部分进行讲解

    转发至https://blog.csdn.net/thundermrbird/article/details/52231639

    展开全文
  • 二分图匹配

    2015-08-08 14:47:13
    设G是一个图。如果存在VG的一个划分X,Y,使得G的任何一条边的一个端点在X中,另一个端点在Y中,则称G为二分图,记作G=(X,Y,E)。如果G中X的每个顶点都与Y的每个顶点相邻,则称G为完全二分图
  • 二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
  • python实现二分图判别
  • 二分图匹配(一)

    2020-11-30 20:37:38
    文章目录什么是二分图:例题:NC111768 CF741C题目描述:题解:代码:二分图最大匹配匈牙利算法算法思想:代码:König定理二分图最优匹配KM(Kuhn-Munkres)算法算法思路:具体操作代码:复杂度 什么是二分图二分...

    什么是二分图:

    二分图充分必要条件条件:
    至少有两个顶点且没有奇环

    二分图判断:
    通过黑白染色

    例题:

    NC111768 CF741C

    题目描述:

    有n对情侣(2n个人)围成一圈坐在桌子边上,每个人占据一个位子,要求情侣不能吃同一
    种食物,并且桌子上相邻的三个人的食物必须有两个人是不同的,只有两种食物(1或者是2),问一种可行分配方式。

    题解:

    如果我们能把不能吃同一种食物的人连边,问题就变成二分图黑白染色
    • 所以情侣关系等价于两者之间连一条边
    • “每连续的三个人不能都一样”怎么办?
    • 让第2i个人和第2i+1个人不能吃一样的食物即可(即1连2,3连4,5连6以此类推)
    • 这样肯定是个二分图——2i和2i-1分别连了他两的情侣,情侣又分别连他两的一个邻居……
    每次都是给这个可能存在的环加两个点,所以有环就一定不是奇环

    构造方法如下:首先情侣连边,然后在原图的相邻点对上,隔一对连一条边

    代码:

    二分图最大匹配

    促成更多的点配对

    匈牙利算法

    有一场宴会,男孩和女孩组成舞伴,并且他们必须互相喜欢才能成为舞伴,一个男孩可能喜欢0个或多个女孩,一个女孩也可能喜欢0个或多个男孩,但一个男孩和他喜欢地女孩成为舞伴之后就不能和其他他喜欢地女孩成为舞伴,女孩亦是如此。请问最多可以有多少对舞伴。

    算法思想:

    对于一个男孩子x,如果他喜欢女孩y,且y还没有舞伴——让他们配对
    • 如果y有了舞伴,x还是会去尝试邀请y,如果y发现她的舞伴z可以换一个舞伴,y就主动抛弃掉z(在确定z可以和别人牵手之后),和x成为舞伴

    增广路(交错路)
    路径的起点和终点都是还没有匹配过的点,并且路径经过的连线是一条没被匹配、一条已经匹配过,再下一条又没匹配这样交替地出现。找到这样的路径后,显然路径里没被匹配的连线比已经匹配了的连线多一条,于是修改匹配图,把路径里所有匹配过的连线去掉匹配关系,把没有匹配的连线变成匹配的,这样匹配数就比原来多1个。

    代码:

    时间复杂度:
    邻接矩阵O(n^3)
    邻接表:O(n*m)

    bool dfs(int x) 
    {
    	for(int i=1;i<=n;i++)//遍历女生 
    	{
    		if(!a[x][i]||vis[i])continue;//没连线或者已被找过 
    		vis[i]=1;
    		if(link[i]==0||dfs(link[i]))//link[i]表示第i个女生的男伴是谁 
    		{
    			link[i]=x;
    			return 1;
    		}
    	}
    	return 0;
    }
    
    int main()
    {
    	for(int i=1;i<=n;i++)//遍历男生 
    	{
    		memset(vis,0,sizeof(vis));//vis[i]第i个女生在这次找搭档的过程中被邀请 
    		sum+=dfs(i);
    	}
    }
     
    

    König定理

    二分图中最大匹配数等于这个图中的最小点覆盖数

    最小点覆盖:
    每个点覆盖以它为端点的所有边,选择最少的点来覆盖所有的边
    (选最少的人,联系到其他的所有的人)
    证明:
    视频时间:01:03:42

    二分图最优匹配

    存在边权,问最大匹配下的最大边权

    KM(Kuhn-Munkres)算法

    最优匹配是建立在完美匹配的基础上的,如果不存在完美匹配,那么本算法失效(但是,我们可以人为连一些权值为0的边,甚至加点,使得没有匹配的节点们最后都有一个“虚假”的匹配)。

    算法思路:

    最开始将每个左边节点连的权值最大的边视为有效边,在匹配给过程当中如果某个点找不到匹配点,则选择将一些无效边改成有效边继续去匹配,选择的这些无效边其实是换掉的原来的某条有效边,那么我们肯定选换掉的代价最小的。
    先让所有人选最佳搭档,当发生冲突时,让降低标准最少的人来换搭档

    具体操作

    给每个点预设一个顶标,只有两个端点的顶标加起来等于边权的边,我们才认为是有效边,
    即L[x]+R[y]==w[x][y]的时候才是有效边
    • 最开始左集合的每个点的顶标为他连出去权值最大的边的权值,右集合每个点顶标为0,当匹配失败的时候,我们遍历之前的左集合本次尝试匹配遍历过的点,在他们的连向右集合未遍历的点的边中找一个与顶标和差值最小的边,即delta=w[x][y]-L[x]-R[y]最小的边(可理解为找出一条损失最小的找出一条增广路。)找到之后修改顶标:左侧所有遍历过的点减去
    delta,右边所有遍历过的点加上delta,这样原来的有效边还是有效边,而我们新加的边也已经加上了。
    • 重复找匹配+修改顶标的操作,一直到找到一个完美匹配即可
    在这里插入图片描述
    详细过程:
    降低的标准x,左边-x,右边+x
    在这里插入图片描述
    每个人都要为了团队牺牲自己,甘愿降低标准

    代码:

    lx[]//左端点,赋值为0x7f 
    ly[]//右端点,赋值为0
    link[i]=j//第i个人匹配的是j 
    int dfs(int x)
    {
    	visx[x]=1; 
    	for(int i=1;i<=m;i++)
    	{
    		if(!visy[i]&&lx[x]+ly[i]==w[x][i])//有边且为有效边 
    		{
    			visy[i]=1;
    			if(link[i]==-1||dfs(link[i]))
    			{
    				link[i]=t;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    memset(ly,0,sizeof(ly));
    memset(lx,0xf7,sizeof(lx));
    memset(link,-1,sizeof(link));
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		lx[i]=max(w[i][j],lx[i]);//最心动的边 
    	}
    } 
    for(int i=1;i<=n;i++)
    {
    	while(1)//全部找到完匹配才能结束 
    	{
    		memset(visx,0,sizeof(visx)); 
    		memset(visy,0,sizeof(visy)); 
    		if(dfs(i))break;//已经给第i人找到匹配
    		int d=0x7f7f7f7f; 
    		for(int j=1;j<=n;j++)
    		{
    			if(visx[j])//要降低标准的男生 
    			{
    				for(int k=1;k<=m;k++) 
    				{
    					if(!visy[k])//引入新的女生 
    						d=min(d,lx[j]+ly[k]-w[j][k]);//求最小的代价 
    				}
    			}
    		}
    		for(d==0x7f7f7f7f)return -1;//匹配失败 
    		for(int j=1;j<=n;j++)if(visx[j])lx[j]-=d;
    		for(int j=1;j<=m;j++)if(visy[j])ly[j]+=d;
    	}
    }
    //n<=m 
    //保证所有男生都匹配(左点),女生不一定 
    

    复杂度

    在这里插入图片描述
    ·如果卡n^2*m可以用网络流来做

    代码:

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #define N 505
    #define M 250005
    #define INF 9990365505
    #define ll long long
    using namespace std;
    int n,m,x,y,z,tot,tim,l,r,q[N],fr[N],nxt[M],d1[M],d2[M];
    int pre[N],visx[N],visy[N],mchx[N],mchy[N];
    ll ex[N],ey[N],slack[N];
    void add(int x,int y,int z)
    {
        tot++;
        d1[tot]=y;
        d2[tot]=z;
        nxt[tot]=fr[x];
        fr[x]=tot;
    }
    void modify(int cur)
    {
        for (int x=cur,lst;x;x=lst)
            lst=mchx[pre[x]],mchx[pre[x]]=x,mchy[x]=pre[x];
    }
    void bfs(int cur)
    {
        for (int i=1;i<=n;i++)
            slack[i]=INF,pre[i]=0;
        l=1,r=0;
        q[++r]=cur;
        ++tim;
        for (;;)
        {
            while (l<=r)
            {
                int u=q[l];
                l++;
                visx[u]=tim;
                for (int i=fr[u];i;i=nxt[i])
                {
                    int v=d1[i],cost=d2[i];
                    if (visy[v]==tim)
                        continue;
                    ll del=ex[u]+ey[v]-cost;
                    if (del<slack[v])
                    {
                        slack[v]=del;
                        pre[v]=u;
                        if (!del)
                        {
                            visy[v]=tim;
                            if (!mchy[v])
                            {
                                modify(v);
                                return;
                            }
                            q[++r]=mchy[v];
                        }
                    }
                }
            }
            ll del=INF;
            for (int i=1;i<=n;i++)
                if (visy[i]!=tim)
                    del=min(del,slack[i]);
            l=1,r=0;
            for (int i=1;i<=n;i++)
            {
                if (visx[i]==tim)
                    ex[i]-=del;
                if (visy[i]==tim)
                    ey[i]+=del; else
                    slack[i]-=del;
            }
            for (int i=1;i<=n;i++)
                if (visy[i]!=tim && !slack[i])
                {
                    visy[i]=tim;
                    if (!mchy[i])
                    {
                        modify(i);
                        return;
                    }
                    q[++r]=mchy[i];
                }
        }
    }
    void KM()
    {
        for (int i=1;i<=n;i++)
            bfs(i);
        ll ans=0;
        for (int i=1;i<=n;i++)
            ans+=ex[i]+ey[i];
        printf("%lld\n",ans);
        for (int i=1;i<=n;i++)
            printf("%d ",mchy[i]);
        putchar('\n');
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            ex[i]=-INF,ey[i]=0;
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            ex[x]=max(ex[x],(ll)z);
        }
        KM();
        return 0;
    }
    
    展开全文
  • 二分图匹配详解

    千次阅读 2019-10-24 16:56:14
    1.二分图的原始模型及相关概念 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)G=(V,E)是一个无向图。如顶点集VV 可分割为两个互不相交的子集,并且图中每 条边依附的两个顶点都分属两个不同的子集。则称...
  • 可以用而二分图来解决匹配的问题。 二分图 二分图又称作偶图,是图论中一个特殊的模型。设G =(V,E)是一无向图,若顶点 V 可以分割为两个互不相交的子集 A 和 B 且图中每条边(i,j)所关联的两个顶点 i 和 j ...
  • 总结的非常全的ACM图论关于二分图的资料 代码很详细 图文并茂
  • 1、背景 在生活中常常遇到两组元素多对多匹配而又数目有限的情况,我们需要对其进行最大匹配数的分配,使效率...2、二分图定义 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可...
  • 算法讲解:二分图匹配

    万次阅读 多人点赞 2016-08-23 10:17:36
    二分图匹配,自然要先从定义入手,那么二分图是什么呢? 二分图: 二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所...
  • 网络流的一个经典应用是二分图匹配。 匹配是指:两两没有公共点的边集。 二分图是指:可以把结点集分成两部分X和Y,使得每条边恰好一个端点在XXX,另一个端点在YYY。换句话说,同色节点不相邻,进行二染色。 一般在...
  • 这是做建模作业是用的的二分图匹配算法 原题如下 该代码测试数据如下 1 1 1 2 2 1 3 1 3 2 4 2 5 3 5 4 5 5 6 1 7 3 7 4 8 2 8 3 测试结果如图 #include <stdio.h> #include <stdlib.h> #include<...
  • 一个实现最近邻二分图匹配的程序,通过将两帧之间的数据的位置信息进行匹配
  • 二分图匹配之HK算法(知识点总结)

    千次阅读 2019-07-19 21:56:59
    每次把所有没有被匹配的当做距离0多源bfs,对当前匹配的进行距离分层, 匈牙利算法每次对于一个点搜所有边只搜到一条路径,不管长短,所以是O(n*m); 而HK算法每次处理所有长度为d的增广路,将其用一次O(m)的...
  • 首先得知道什么是二分图匹配问题,给出一个二分图,每个人与另外的一个或者多个人存在某种关系  问将他们两两配对的对,最多能配成多少对。  其次,明确几个专业名词。  最大匹配:边数最多的匹配成为最大匹配...
  • 这是一个标准的求二分图最大匹配的问题,求解的思路有两种: 转化为最大流问题 匈牙利算法 转化为最大流问题: 在原图的两侧分别增加一个源点 s s s 和一个汇点 t t t ,如下图所示: 这样二分图的 ...
  • 匈牙利算法 什么是匈牙利算法 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始... 以上均是书上语言,简单来说匈牙利算法就是用来求解二分图匹配问题 的; 思路 接下来我们来...
  • 概述: 匈牙利算法是一种借助增广路来求二分图最大匹配问题的算法 增广路: 从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路 如上图所示,9-4-8-1-6-2就是一条...
  • 二分图匹配及其应用(刘汝佳).ppt
  • 带权二分图匹配-KM算法

    千次阅读 2018-11-26 22:46:45
    KM算法:解决带权二分图最优匹配 2.KM算法流程 1.为各顶点赋值值,将左顶点赋值为最大权值,右顶点赋值为0 2.用匈牙利算法寻找完备匹配 3.若未找到完备匹配则修改顶点权值 4.重复(2)(3)直到找到完备匹配为止 ...
  • 最佳二分图匹配算法(总结)

    千次阅读 2018-07-20 16:35:13
    通过调整加权完全二分图的可行顶标,将加权完全二分图转化为无权二分图,使得加权完全二分图的最佳匹配与转化后的无权二分图的最佳匹配相同,在此基础上采用匈牙利算法。 最小费用最大流算法 O(n*e) 将带权二分图...
  • 数学建模常用经典算法集合均已成功编译-二分图最大匹配算法BGMMA.rar 数学建模常用经典算法集合(均已成功编译) 扰!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 29,474
精华内容 11,789
关键字:

二分图匹配