首页 > 代码库 > 图论2——二分图与匈牙利算法

图论2——二分图与匈牙利算法

2024-09-15 01:30:23   218人阅读

一般情况下，我们用的都是简单图。带权图，无向图；还有各种算法，像Floyd，SPFA，Dijkstra……

但是，在我们需要进行一些匹配问题的时候，我们就不能够只是用简单图了，不然最终可能会收获TLE（超时）。

这个时候，我们就要让二分图出场了！

1、二分图的应用

我们举一个最简单的例子。有N名男运动员和M名女运动员要组成尽可能的多的混双配对，其中有一些不能够配对，请问如何处理？

这时候，大家就可能比较头疼——没有什么思路。各种数据结构似乎也都无能为力，组合数论看起来可以，实际上也算不出来，更不会有人想到这是图论。

然而这就是一道二分图模板题。

【题目大意】

有N名男运动员和M名女运动员要组成尽可能的多的混双配对，其中有一些不能够配对，请问如何处理？

【输入格式】

第一行 输入三个整数，N,M,K，，表示男运动员的个数，女运动员的个数，以及可匹配对数。

以下K行，每行两个整数a,b，表示男运动员a,b可以配对比赛。

【输出格式】

只有一个整数，为最多的混双配对。

【输入样例】

5 4 14

1 1

1 2

2 3

3 2

4 2

4 3

4 4

5 4

5 2

5 3

3 3

2 4

1 3

2 1

【输出样例】

4

【算法分析】

我们之前已经分析过它是一道图论题，但是怎么建图呢？

如果我们把每一个运动员看做图的顶点V，将每一对可配对的连接，则上面的样例可以表示为下图（无向图）。技术分享

那么你会做了吗？

其实上面这张图就是一张二分图。二分图的定义大致如下。

图G=[V,E]是一个无向图，顶点集合V分为X和Y两部分，G中的每一条边一定一个端点在X，一个端点在Y。

所以，二分图也可以记为G=[X,Y,E]。

我们也知道，有一种东西叫做完全二叉树，那么有没有完全二分图呢？

当然有。当X中的任意结点都与Y中的地所有节点连接时，它就是一个完全二分图（因为是无向图，所以亦可为Y中的节点与X中所有节点连接）。

【定理】

当且仅当无向图G的每一个回路长度均为偶数时，该图才是一个二分图。（包括无回路的情况）

题目中的求尽可能多的混双配对，其实也就是求二分图的最大匹配。

2、二分图的最大匹配

要解决二分图的最大匹配问题，我们有几种算法，例如网络流。但是，今天我要讲的，是Edmonds在1965年提出的匈牙利算法（Hungary Algorithm）。

首先，我们来了解一些名词。在这里，我们暂时设M为一张二分图中可能出现的最大匹配方案。

交错轨

设P是二分图中的一条路径，如果该路径任意两条相邻边一条在M内（是最大方案的一部分），另一条不在M内（不是最大方案的一部分），那么它就是一条交错轨。

特别的，如果该路径中只有一条边，那么他一定是一条 交错轨，不论在M内外。

可增广轨

我们再定义一个点“是否有连接着最大匹配方案里的边”为这个点是否被“盖住”。如果交错轨的两个定点都是没有被“盖住”的，那么他就是一个可增广轨。

为什么要寻找可增广轨呢？因为，如果你在寻找最大匹配方案时能够找到一个可增广轨的话，那么最大匹配方案就可以增加到当前方案匹配数+1。

技术分享

讲了这么多，现在开始讲一讲匈牙利算法。

他其实就是最开始把最大匹配方案M置为空集，然后反复寻找增广路径，知道没有为止，就这么简单。

增广路径的找法，就是DFS或BFS。在针对稠密图时建议DFS，反之则为BFS。

下面，给出DFS的Cpp参考代码。

#include<cstdio>
#include<cstring>
const int MAX=1001;
int n,m,k;
int link[MAX];
bool vis[MAX];
bool map[MAX][MAX];
bool dfs(int a)
{
    for(int i=1;i<=m;i++)
        if(map[a][i]==1&&!vis[i])
        {
            vis[i]=1;
            if(!link[i]||dfs(link[i]))
            {
                link[i]=a;
                return 1;
            }
        }
    return 0;
}
int main()
{
    int a,b,ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d",&a,&b);
        map[a][b]=1;
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

关于BFS，这里同样给出示范性的Cpp代码。

#include<cstdio>
#include<cstring>
const int MAX=1001;

struct link
{
    int data;
    link *nxt;
    link(int=0);
};
link::link(int n)//类继承 
{
    data=n;
    nxt=NULL;
}
int n,m,k,ans=0;
int res[MAX];
bool state[MAX];
link *head[MAX],*lst[MAX];

bool bfs(const int n)
{
    link* t=head[n];
    while(t!=NULL)
    {
        if(!state[t->data])
        {
            state[t->data]=1;
            if(!res[t->data]||bfs(res[t->data]))
            {
                res[t->data]=n;
                return 1;
            }
        }
        t=t->nxt;
    }
    return 0;
}
int main()
{
    int a,b;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d%d",&a,&b);
        if(lst[a]==NULL)
            lst[a]=head[a]=new link(b);
        else
            lst[a]=lst[a]->nxt=new link(b);
    }
    for(int i=1;i<=n;i++)
    {
        memset(state,0,sizeof(state));
        if(bfs(i))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

本篇博客到这里就结束了，希望大家能满意，然后点个赞，谢谢！

图论2——二分图与匈牙利算法


联系
我们