匈牙利匹配算法

Ⅰ fp一个匹配问题（匈牙利算法）

program p1557;
var
i,j,m,n,x,y,tot,v:longint;
link:array[1..200] of longint;
cover,f:array[1..200] of boolean;
map:array[0..200,0..200] of boolean;

Function work(i:longint):boolean;
var
q,k:longint;
begin
work:=true;
for k:=1 to n do
if (map[i,k]=true) and (cover[k]=false) then
begin
q:=link[k];
link[k]:=i;
cover[k]:=true;
if (q=0) or (work(q)=true) then exit;
link[k]:=q;
end;
work:=false;
end;

Begin
assign(input,'i.i'); reset(input);
assign(output,'o.o'); rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=true;
repeat
readln(x,y);
map[y,x]:=false;
until (x=0) and (y=0);
for i:=1 to n do
begin
for j:=1 to n do
cover[j]:=false;
work(i);
end;
tot:=0;
for i:=1 to n do
begin
j:=link[i];
link[i]:=0;
map[j,i]:=false;
for v:=1 to n do cover[v]:=false;
if (work(j)=false) then
begin
tot:=tot+1;
writeln(j,' ',i);
end;
map[j,i]:=true;
link[i]:=j;
end;

if tot=0 then writeln('none')

end.

Ⅱ 什么是匈牙利算法

谈匈牙利算法自然避不开Hall定理，即是：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A，和A邻接的点集为T(A)，恒有： │T(A)│ >= │A│
匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束，否则进行第3步；
3．在X中找到一个非饱和顶点x0，作V1 ← {x0}, V2 ← Φ；
4．若T(V1) = V2则因为无法匹配而停止，否则任选一点y ∈T(V1)\V2；
5．若y已饱和则转6，否则做一条从x0 →y的可增广道路P，M←M?E(P)，转2；
6．由于y已饱和，所以M中有一条边(y,z)，作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}， 转4；

设数组up[1..n] --- 标记二分图的上半部分的点。
down[1..n] --- 标记二分图的下半部分的点。
map[1..n，1..n] --- 表示二分图的上，下部分的点的关系。
True-相连， false---不相连。
over1[1..n]，over2[1..n] 标记上下部分的已盖点。
use[1..n，1..n] - 表示该条边是否被覆盖 。

首先对读入数据进行处理 ，对于一条边(x，y) ，起点进集合up，终点进集合down。 标记map中对应元素为true。

1. 寻找up中一个未盖点 。
2. 从该未盖点出发 ，搜索一条可行的路线 ，即由细边出发， 由细边结束， 且细粗交错的路线 。
3. 若找到 ，则修改该路线上的点所对应的over1，over2，use的元素。重复步骤1。
4. 统计use中已覆盖的边的条数total，总数n减去total即为问题的解。

Ⅲ 匈牙利算法在计算机C++语言编程中怎么应用

匈牙利算法是图论中完成二分图匹配的经典算法之一.输入排队的Crossbar调度算法是以获得交换机的输入端口和输出端口最大匹配,从而得到高吞吐量为目的.因而在调度算法理论研究中应用了二分图最大匹配的Maximum Size Matching(MSM)和 Maximum Weight Matching(MWM)算法成为各种调度算法性能的评价标准.文中介绍了匈牙利算法在输入排队调度算法仿真中的应用,并且得出相应典型算法的性能仿真曲线,从而为进一步研究调度算法打下理论基础.

Ⅳ 二分图匹配 匈牙利算法

1匹配K..然后假设从M找增广路时,找到了K点,这时LInk[k]=1..那么再重新从1找增广路.如果找到L，
则1与L匹配成功,M则与K匹配

Ⅳ 什么叫匹配特性

匹配一词单独拿出来是可以解释的！！！但是 把“匹配特性”连在一起 首要 要了解条件 是什么样的东西或物品之间的匹配

匹配（先解释一下搜到的）：
匹配 pǐpèi
(1)成为夫妇关系
(2) 配合;搭配
(3) [无线电元器件等]配合
(4) 阻抗匹配
(5) [计算机]给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
图的匹配

[编辑本段]概念
1.图的定义
无向图：无向图G是指非空有限集合VG，和VG中某些元素的无序对的集合EG，构成的二元组(VG，EG)。VG称为G的顶点集，其中的元素称为G的顶点。EG称为G的边集，其中的元素称为G的边。在不混淆的情况下，有时记V＝VG，E＝EG。如果V＝{v1,…,vn}，那么E中的元素e与V中某两个元素构成的无序对(vi，vj)相对应，记e＝vivj，或e＝vjvi。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。
二分图：设G是一个图。如果存在VG的一个划分X，Y，使得G的任何一条边的一个端点在X中，另一个端点在Y中，则称G为二分图，记作G＝(X，Y，E)。如果G中X的每个顶点都与Y的每个顶点相邻，则称G为完全二分图。
2.匹配的相关概念
设G＝(V，E)是一个图， ，如果M不含环且任意两边都不相邻，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。
对于图G＝(V，E)，在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义 ，并称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果对一切，e∈E，w(e)=1,则G的最大权匹配就是G的最大匹配。
设M是图G=(V,E)的一个匹配，vi∈V。若vi与M中的边相关联，则称vi是M饱和点，否则称vi为M非饱和点。
如果G中每个顶点都是M饱和点，则称M为G的完美匹配。
设M是G的一个匹配，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M交错链。类似地，我们可以定义G的交错圈。易知，G的交错圈一定是偶圈。
一条连接两个不同的M非饱和点的M交错链称为M增广链。
两个集合S1与S2的“异或”操作S1⊕S2是指集合S1⊕S2＝（S1∩S2）\（S1∪S2）
容易看出，设M是G的匹配，P是G中的M增广链、则M⊕P也是G的匹配，而且 。
图表 1 “异或”操作
可以证明，G中匹配M是最大匹配当且仅当G中没有M增广链。
匹配算法
1.二分图的最大匹配
设有M个工人x1, x2, …, xm，和N项工作y1, y2, …, yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。
人员分配问题可以用图的语言来表述。令X={x1, x2, …, xm}，Y={y1, y2, …,yn}，构造二分图G=(X, Y, E)如下：
对于1≤i≤m，1≤j≤n，当且仅当工人xi胜任工作yi时，G中有一条边xiyi，于是人员分配问题就成为在G中求一个最大匹配的问题。
求最大匹配常用匈牙利算法，它的基本思想是：对于已知的匹配M，从X中的任一选定的M非饱和点出发，用标号法寻找M增广链。如果找到M增广链，则M就可以得到增广；否则从X中另一个M非饱和点出发，继续寻找M增广链。重复这个过程直到G中不存在增广链结束，此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法，因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。
图表 2 匈牙利算法
理解了这个算法，就不难写出人员分配问题的解答了。在给出程序之前，先做一些假设：
为了简单起见，假设工人数等于工作数，即N=M，且N≤100，这里，N也可以看作是二分图的|X|和|Y|。
数据从文件input.txt中读入，首先是N和|E|，下面|E|行每行两个数(I, J)，表示工人I可以胜任工作J，即二分图中的边xiyj。
结果输出到文件output.txt，第一行是最大匹配数s，下面s行每行两个数(I, J)，表示分配工人I做工作J，即匹配边xiyj。
下面是人员分配问题的参考解答，该算法的时间复杂度为O(n3)。
2.二分图的最大权匹配
对于上面的人员分配问题，如果还考虑到工人做工的效率，就可以提出所谓的分派问题：应该怎样分配才能使总的效率最大？
同上一节，我们可以构造一个二分图G，如果把工人xi做工作yi的效率wij看作是G中边xiyi的权，则分派问题就相当于在赋权二分图G中求一个最大全匹配。
由线性规划的知识，求二分图G的最大权匹配，只需在匈牙利算法的基础上少许改进即可。它的基本思想是，对二分图的顶点编号，然后根据编号构造一个新的二分图G’，最后把求G的最大权匹配转换为求G’的完美匹配。
下面的这条定理是这个算法的理论基础。
定理：设 是赋权图（权非负）的完全二分图 的一个完美匹配，这里 。如果存在一组 ，满足 ，并且对一切 ，均有 ，则 是 的最大权匹配。
下面，给出求最大权匹配的程序。输入文件中首先是N和|E|，下面|E|行每行三个数(I, J, W)，表示工人I做工作J的效率是W。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算法的时间复杂度也是O(n3)。
3. 任意图的匹配
任意图的最大匹配算法也是建立在找增广链的基础上的，只是任意图的增广链要比二分图难找得多。这个算法比较复杂，竞赛中也很少用到，因此，这里就不做详细介绍了。

Ⅵ 如何通俗地解释匈牙利算法

是指二分图匹配的这个算法吧？下面是复制的，原文有图
原文地址：http://blog.csdn.net/lw277232240/article/details/72615522

二分图匹配，江湖称二分匹配，图论相关算法。

现在给出两个集合，我们拿约会来举例子。一方是男生集合，一方是女生集合，女生都比较内敛，对不认识的男孩纸并不喜欢一起约会，所以这里边就要有人际关系的问题了。

这里给男生编号n1,n2.....nn;女生编号v1v2....vn；

下面给出女生认识的男生的列表：
v1 :n1 ,n2.

v2 :n2, n3.

v3 : n1.

这里显而易见，1号男生2号男生是比较受欢迎的哈~。不用算法思想的去想这个问题我们可以这样思考：三号女生只认识1号男生，匹配上。（1组搞定）这个时候一号女生就不能选择1号男生了，她只能去选2号男生，这时候2号女生也就有了自己能选择的男生，这里我们就匹配成功了：

v1 n2

v2 n3

v3 n1

这里我们就完成了匹配的过程，这个时候我们因为所有人都有了约会对象，我们这个时候称之为最大匹配，同时也是完美匹配。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

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

那么我们要如何实现算法呢？因为代码是不能直接看出来如何匹配能得到最大匹配的，所以我们这里就要有一个顺序去寻找最大匹配，这里我们以编号大小的顺序来寻找约会对象。
从v1开始找，先找到了n1.约上，然后是v2,找到了n2,约上。v3找到了n1,但是这里n1和v1已经约好了，怎么办呢？v1对v3说：我还认识n2,我去问问他有没有约会人选，要是没有的话，n1让给你。（其实我想说她是傻逼。。。。）然后v1去找n2,但是n2和v2约上了，这个时候呢v2对v1说：我还认识n3,我去看看他有没有约会的人选，要是没有的话n2，让给你（这两个傻逼。。。。）然后v2找到了n3,n3乐的屁颠屁颠的，说正好没人约我，然后他俩约上了，v2找到了n3,那么v1就能和v2约上了，然后v3也就能和n1约上了，我们这个时候就从刚刚的两组匹配，转到了3组匹配。

刚刚所述的过程，其实就是在找增广路。（这里增广路的含义自己就可以理解了吧~）那么我们如何用代码实现这个过程呢？其实并不难，我们这里需要三个数组，一个是图，一个是询问vis标记，一个是match匹配。
出自：http://blog.csdn.net/lw277232240/article/details/72615522
原文有图

Ⅶ 匈牙利法中直线覆盖选择的最小值

匈牙利法中直线覆盖选择的最小值：二分图最大匹配数=最小点覆盖率。

二分图的最小点覆盖的理解：找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择。最大独立数：选取最多的点，使任意所选两点均不相连。

最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

匈牙利算法

匈牙利算法（Hungarian algorithm），其核心就是寻找增广路径，是一种用增广路径求二分图最大匹配的算法。匈牙利算法是一种在P问题内（多项式时间内）求解任务分配问题的组合优化算法。它推动了后来的原始对偶方法。

匈牙利算法是美国数学家哈罗德·库恩于1955年提出的。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

Ⅷ 程序员必须掌握哪些算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

Ⅸ 用匈牙利算法求最大匹配唯一么

不惟一。扩张的顺序不同，枚举顶点的顺序不同，解就不一定相同