首页 > 代码库 > 【模板】匈牙利算法
【模板】匈牙利算法
匈牙利算法用于二分图匹配
还有几个知识点:
最大匹配数:最大匹配的匹配边的数目
最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择
最大独立数:选取最多的点,使任意所选两点均不相连
最小路径覆盖数:对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。
定理1:最大匹配数 = 最小点覆盖数(Konig定理)
定理2:最大独立集 = 顶点数-最大匹配
定理3:最小路径覆盖数 = 原图顶点数 - 对应二分图最大匹配数
Hall定理:设二分图中G=<V1,V2,E>中|V1|=m<=|V2|=n,G中存在从V1到V2的完备匹配当且仅当V1中任意k(k=1,2,...,m)个顶点至少与V2中k个顶点相邻。
关于DAG的建图:对于原DAG的每个点p,拆成p和p‘,如果有一条q->p的边,就在二分图中连q->p‘。
更多内容参见:《浅谈图的匹配算法及其应用》 陈胤伯
1 #include<stdio.h> 2 #include<string.h> 3 #define maxn 1000 4 int ans,n,m,edg,pp[maxn]; 5 bool vis[maxn],graph[maxn][maxn]; 6 int dfs(int); 7 int main() 8 { 9 scanf("%d%d%d",&n,&m,&edg);10 int i,p,q;11 for(i=1;i<=edg;i++)12 {13 scanf("%d%d",&p,&q);14 graph[p][q] = true; 15 }16 for(i=1;i<=n;i++)17 {18 memset(vis,false,sizeof(vis));19 ans += dfs(i);20 }21 printf("%d",ans);22 return 0;23 }24 int dfs(int now)25 {26 for(int i=1;i<=m;i++)27 {28 if(vis[i]||!graph[now][i]) continue;29 vis[i] = true;30 if(!pp[i]||dfs(pp[i]))//这句一定要注意 31 {32 pp[i] = now;33 return 1;34 }35 }36 return 0;37 }
【模板】匈牙利算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。