[学习笔记]匈牙利算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[学习笔记]匈牙利算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1410字，纯文字阅读大概需要3分钟。

内容图文

壹、模板测试链接

传送门

贰、说明

完美匹配一定是最大匹配，而最大匹配不一定是完美匹配.

交错路径：给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径.

而如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径叫做M-增广路径.

当图中再没有增广路径了，就意味着我们找到了该图的最大匹配了

二部图：给定两组顶点，但是组内的任意两个顶点间没有边相连，只有两个集合之间存在边，即组1内的点可以和组2内的点相连，这样构建出来的图就叫做二部图.

最大匹配是互相的，如果我们给X找到了最多的Y中的对应点，同样，Y中也不可能有更多的点得到匹配了

1. 匈牙利算法寻找最大匹配，就是通过不断寻找原有匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M' , 其恰好比M 多一条边.

2. 对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的.

这就是匈牙利的实现过程了.

叁、代码

using namespace Elaina;

const int maxn=500;
const int maxm=5e4;

struct edge{int to,nxt;}e[maxm+5];
int tail[maxn+5],ecnt;

int x,y,m;

inline void add_edge(const int u,const int v){
    e[++ecnt]=edge{v,tail[u]};tail[u]=ecnt;
}

inline void input(){
    x=readin(1),y=readin(1),m=readin(1);
    int u,v;
    rep(i,1,m){
        u=readin(1),v=readin(1);
        add_edge(u,v);
    }
}

int vis[maxn+5],match[maxn+5];
int dfs(const int u){
    for(int i=tail[u],v;i;i=e[i].nxt)if(!vis[v=e[i].to]){
        vis[v]=1;
        if(!match[v] || dfs(match[v])){
            match[v]=u;
            return 1;
        }
    }
    return 0;
}

signed main(){
    input();
    int ans=0;
    rep(i,1,x){
        memset(vis+1,0,y<<2);
        if(dfs(i))++ans;
    }
    writc(ans,'\n');
    return 0;
}

内容总结

以上是互联网集市为您收集整理的[学习笔记]匈牙利算法全部内容，希望文章能够帮你解决[学习笔记]匈牙利算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---