匈牙利匹配演算法

Ⅰ 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)

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

不惟一。擴張的順序不同，枚舉頂點的順序不同，解就不一定相同