正文

匈牙利算法&模板

IP云V管理员/2022-11-25/2 阅读

11/25

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

匈牙利算法

一. 算法简介

匈牙利算法是由匈牙利数学家Edmonds于1965年提出。该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

二分图的定义：

设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集V1,V2，那么称此图G为二分图。

例如，下图就是一个二分图：

二分图的匹配：

二分图中的子图中，每个节点只连一条边，则称该子图是二分图中的一个匹配。

极大匹配：

无法再向二分图中加入边，使得满足匹配条件。

最大匹配：

所有极大匹配中边数最多的一个匹配。

完美匹配 ：

如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

方法：

求最大匹配的一种显而易见的算法是:先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级。因此，需要寻求一种更加高效的算法。下面介绍用增广路求最大匹配的方法。

算法图解：

下图是一个二分图，现在求最大匹配。

先从1出发，找增广路，找到1->A 这条路，标记并记录。

从2出发，找到2->B这条路，标记并记录。

从3开始找，发现3所连接边全部被占用，这时进行一个神奇的操作：

从三开始找一条增广路，3 -> A -> 1 -> B -> 2 -> C

这时，在图中将有两种颜色的边删去，留下绿色的边。

这时，这张图的最大匹配值就是3.

三.算法模板

核心代码：

 bool Hungary ( int x ) {

          for ( int i = head[ x ] ; i ; i = E[ i ] . next ) {

                  if ( vis[ i ] ) continue ;

                  int temp = E[ i ] . to ;

                  vis[ i ] = true ;

                  if ( !match[ temp ] || Hungary ( match[ temp ] ) ) {

                           match [ temp ] = x ;

                           return true ;

                  }

          }

          return false ;

 }

主程序：

for ( k= ; k<=M ; ++k ) {

                 memset ( vis , false , sizeof ( vis ) ) ;

                 if ( !Hungary ( k ) )

                         break ;

}

时间复杂度：

邻接矩阵： O(n ³ )
邻接表： O(nm)

空间复杂度：

邻接矩阵： O(n ² )
邻接表：O(n+m)

2016-09-16 02:18:44

(完)

匈牙利算法&模板的更多相关文章

poj 1274 The Perfect Stall【匈牙利算法模板题】
The Perfect Stall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20874 Accepted: 942 ...

匈牙利算法模板 hdu 1150 Machine Schedule（二分匹配）
二分图:https://blog.csdn.net/c20180630/article/details/70175814 https://blog.csdn.net/flynn_curry/artic ...

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

HDU 2444 - The Accomodation of Students - [二分图判断][匈牙利算法模板]
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=2444 Time Limit: 5000/1000 MS (Java/Others) Mem ...

HDU 1045 - Fire Net - [DFS][二分图最大匹配][匈牙利算法模板][最大流求二分图最大匹配]
题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1045 Time Limit: 2000/1000 MS (Java/Others) Mem ...

POJ：3041-Asteroids（匈牙利算法模板）
传送门:http://poj.org/problem?id=3041 Asteroids Time Limit: 1000MS Memory Limit: 65536K Description Bes ...

POJ 1325 && 1274：Machine Schedule 匈牙利算法模板题
Machine Schedule Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 12976 Accepted: 5529 ...

POJ 3041 匈牙利算法模板题
一开始预习是百度的算法然后学习了一下然后找到了学长的ppt 又学习了一下.. 发现..居然不一样... 找了模板题试了试..百度的不好用反正就是wa了..果然还是应当跟着学长混.. 图两边的点分 ...

POJ 3041 Asteroids | 匈牙利算法模板
emmmmm 让你敲个匈牙利 #include<cstdio> #include<algorithm> #include<cstring> #define N 51 ...

随机推荐

【翻译十七】java-并发之高性能对象
High Level Concurrency Objects So far, this lesson has focused on the low-level APIs that have been ...

算法系列：HMM
隐马尔可夫(HMM)好讲,简单易懂不好讲. 用最经典的例子,掷骰子.假设我手里有三个不同的骰子.第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1 ...

机器学习公开课笔记(5)：神经网络(Neural Network)——学习
这一章可能是Andrew Ng讲得最不清楚的一章,为什么这么说呢?这一章主要讲后向传播(Backpropagration, BP)算法,Ng花了一大半的时间在讲如何计算误差项$\delta$,如何计算 ...

PHP模拟POST请求，获取response内容
/* * 模拟POST请求,获取response内容 / protected function curl($url, $type, $header, $data) { $CURL_OPTS = ar ...

JS 捕获 input 中键盘按键
JS 捕获 input 中键盘按键的相应处理事件是很简单的,google搜索一下很容易找到处理方式,请看如下一种简单的处理方式: HTML代码: <div> <input typ ...

小甲鱼PE详解之IMAGE_NT_HEADERS结构定义即各个属性的作用（PE详解02）
PE Header 是PE相关结构NT映像头(IMAGE_NT_HEADER)的简称,里边包含着许多PE装载器用到的重要字段.下边小甲鱼将为大家详细讲解哈~ (视频教程:http://fishc.co ...

如何离线下载Chrome的安装包
打开Chrome官网(自行搜索)点击下载后下载的是联网安装包,这对部分上网不方便的用户造成了一定的麻烦. http://www.google.cn/chrome/browser/desktop/ind ...

java判断字符串是否为数字或中文或字母
个人认为最好的方法各种字符的unicode编码的范围: * 汉字:[0x4e00,0x9fa5](或十进制[19968,40869]) * 数字:[0x30,0x39](或十进制 ...

Junit的简单使用
Junit是一个很好用的单元测试工具,下面是使用Junit来测试方法的简单案例: import java.util.ArrayList; import java.util.Iterator; impo ...

android MPAndroidChart饼图实现图例后加数字或文本（定制图例）
转载请注明:http://blog.csdn.net/ly20116/article/details/50905789 MPAndroidChart是一个非常优秀的开源图表库,MPAndroidCha ...

相关阅读

目录[+]