题解 P3386 【【模板】二分图匹配】

· · 题解

半年多前觉得这道题很难，现在觉得还好.

一看题目，

“ 模板 ” 两个大字映入我的眼帘，

谁都知道这是一个二分图匹配问题

本文比较浅显易懂（私以为），适合萌新看，大佬们可跳过

解决二分图最大匹配大概有两种做法，

一. 二分图介绍

二分图是一种特殊的无向图。

• 点集 V 可以拆成两部分 V = V1 ∪ V2。

• V1 内部没有边。

• V2 内部没有边。

• 换句话说，所有的边都横跨 V1 和 V2。

二. 二分图最大匹配

• 匹配：选出图的边集 E 的一个子集 F，使 V1 和 V2 中的每个点

最多关联了 F 中的一条边。

• 最大匹配：选出的子集包含边的个数最大。

三. 增广路定理

设 F 是一个匹配。

• V1, V2 中被 F 覆盖到的点称为饱和点，未覆盖到的叫非饱和点。

• F 中的边称为匹配边，其它的叫非匹配边。

• 交错路：从非饱和点出发，依次经过非匹配边、匹配边、非匹配边、匹配边、非匹配边……

• 增广路：从非饱和点出发最后走到一个非饱和点的交错路。

• 增广路中非匹配边比匹配边多一条。

• 如果图中存在增广路，则把经过的非匹配边和匹配边互换，能得到更大的匹配 F′。 

• 如果 F 不是最大匹配，则存在增广路。

四. 增广路算法

  1. 一开始，F 为空。

  2. 每次找 F 的增广路，能找到就增广。

  3. 找不到增广路时，算法结束。

五. 匈牙利算法

  1. 一开始，F 为空。

  2. 枚举 V1 中的点 x，找以 x 为起点的增广路，找到了就增广。

  3. V1 中的点都尝试增广一次后，算法结束。

定理：如果在某一时刻，找不到以 x 为起点的增广路，则增广几轮之后仍不会找到。

时间复杂度：O(nm)

这是我在一次培训中老师的见解.

关于证明，太难，蒟蒻不会证，大佬们请谅解.

下面贴代码（我相信各位大佬也不需要代码）：

#include<iostream>

using namespace std;

const int V=1000010;
int N,M,E,ans;
int edge[V],head[1010],nxt[V],tot;
int dfn[2020],match[1010],x,y,ti;

void add(int x,int y)//加边
{
    edge[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

int dfs(int x,int ti)//ti是时间戳
{
    for(int i=head[x];i;i=nxt[i])
    {
        int j=edge[i];
        if(dfn[j]!=ti)//这一轮还没有遍历到
        {
            dfn[j]=ti;
            if(!match[j]||dfs(match[j],ti))//没有和j点匹配的点或者是找到了一条可增广的路径
            {
                match[j]=i;//i,j匹配
                return 1;
            }
        }

    }
    return 0;
}

int main()
{
    cin>>N>>M>>E;
    for(int i=1;i<=E;i++)
    {
        cin>>x>>y;
        if(x>N||y>M)  continue;
        add(x,y);
    }

    for(int i=1;i<=N;i++)
        if(dfs(i,++ti))  ans++;//找到了一条增广路

    cout<<ans<<endl;

    return 0;
}

去掉空行后40来行，也是比较短的了.

博客食用口感更好哟

因为有一些小错误，导致定理阐述符号都是？？？？，更改了一下，希望管理员给过