二分匹配演算法

『壹』 詳細講解二分圖匹配中的Hopcroft-Karp演算法

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std; typedef long long ll;const int M = 550; struct node{ int u, v, f, next;}a[5000]; // 需要至少4000，開到5000比較穩int H[1100], d[1100], c[1100];int n, m, cnt;int S, T, N; void add(int u, int v, int f){ a[cnt].u = u; a[cnt].v = v; a[cnt].f = f; a[cnt].next = H[u]; H[u] = cnt++;} void build(int u, int v, int f){ add(u, v, f); add(v, u, 0);} int dfs(int u, int flow){ if (u == T) return flow; int res = 0, tt, detla; for (tt = H[u]; ~tt; tt = a[tt].next){ int v = a[tt].v; int f = a[tt].f; // f > 0才能算 if (f>0&&d[u] == d[v] + 1){ detla = dfs(v, min(f, flow)); a[tt].f -= detla; a[tt ^ 1].f += detla; flow -= detla; res += detla; if (!flow) break; } } if (!res){ if (!--c[d[u]]) d[S] = N; ++c[++d[u]]; } return res;} void isap(){ int i, j; memset(d, 0, sizeof(d)); memset(c, 0, sizeof(c)); c[0] = N; int ans = 0; while (d[S] < N){ ans += dfs(S, INT_MAX >> 2); } printf("%d\n", ans);} int main(){ int k, i, j, t; while (~scanf("%d", &t), t){ scanf("%d%d", &n, &m); memset(H, -1, sizeof(H)); cnt = 0; int u, v; S = 1; T = n + m + 2; N = T; // 從S到女生的邊 for (i = 1; i <= n; i++) { build(S, i + 1, 1); } // 從男生到T的邊 for (i = 1; i <= m; i++) { build(n + 1 + i, T, 1); } for (i = 0; i < t; i++){ scanf("%d%d", &u, &v); // 從男生到女生的邊 // 修改前的代碼會多次創建S到女生的邊和男生到T的邊，造成了1個男生可以和多個女生匹配或者多個男生可以和1個女生匹配的錯誤 build(u + 1, v + n + 1, 1); } isap(); } return 0;}

『貳』 java 二分演算法只能對數字進行查找嗎

2分法查找，前提是要有序，要排序，必然要比較大小，所以只要一個類它實現了Comparable介面的compareTo(To)方法（Comparable在java.lang包中）或是實現一個比較器對象介面Comparator(Comparator在java.util包)，都可以進行比較了。不管是String型,計本數據類型,還是其他什麼的，都可以用2分發查找了。給你看看API

java．util．Collections中2分法的API

binarySearch

publicstatic<T>intbinarySearch(List<?extendsComparable<?superT>>list,

Tkey)使用二分搜索法搜索指定列表，以獲得指定對象。在進行此調用之前，必須根據列表元素的自然順序對列表進行升序排序（通過sort(List)方法）。如果沒有對列表進行排序，則結果是不確定的。如果列表包含多個等於指定對象的元素，則無法保證找到的是哪一個。

此方法對「隨機訪問」列表運行log(n)次（它提供接近固定時間的位置訪問）。如果指定列表沒有實現RandomAccess介面並且是一個大型列表，則此方法將執行基於迭代器的二分搜索，執行O(n)次鏈接遍歷和O(logn)次元素比較。

參數：

list-要搜索的列表。

key-要搜索的鍵。

返回：

如果搜索鍵包含在列表中，則返回搜索鍵的索引；否則返回(-(插入點)-1)。插入點被定義為將鍵插入列表的那一點：即第一個大於此鍵的元素索引；如果列表中的所有元素都小於指定的鍵，則為list.size()。注意，這保證了當且僅當此鍵被找到時，返回的值將>=0。

拋出：

ClassCastException-如果列表中包含不可相互比較的元素（例如，字元串和整數），或者搜索鍵無法與列表的元素進行相互比較。

--------------------------------------------------------------------------------

binarySearch

publicstatic<T>intbinarySearch(List<?extendsT>list,

Tkey,

Comparator<?superT>c)使用二分搜索法搜索指定列表，以獲得指定對象。在進行此調用之前，必須根據指定的比較器對列表進行升序排序（通過sort(List,Comparator)方法）。如果沒有對列表進行排序，則結果是不確定的。如果列表包含多個等於指定對象的元素，則無法保證找到的是哪一個。

此方法對「隨機訪問」的列表運行log(n)次（它提供接近固定時間的位置訪問）。如果指定列表沒有實現RandomAccess介面並且是一個大型列表，則此方法將執行基於迭代器的二分搜索，執行O(n)次鏈接遍歷和O(logn)次元素比較。

參數：

list-要搜索的列表。

key-要搜索的鍵。

c-排序列表的比較器。null值指示應該使用元素的自然順序。

返回：

如果搜索鍵包含在列表中，則返回搜索鍵的索引；否則返回(-(插入點)-1)。插入點被定義為將鍵插入列表的那一點：即第一個大於此鍵的元素索引；如果列表中的所有元素都小於指定的鍵，則為list.size()。注意，這保證了當且僅當此鍵被找到時，返回的值將>=0。

拋出：

ClassCastException-如果列表中包含使用指定的比較器不可相互比較的元素，或者使用此比較器無法相互比較搜索鍵與列表元素。

java．util．Comparator介面。

A>intcompare(To1,To2)比較用來排序的兩個參數。根據第一個參數小於、等於或大於第二個參數分別返回負整數、零或正整數。

在前面的描述中，符號sgn(expression)表示signum數學函數，根據expression的值為負數、0還是正數，該函數分別返回-1、0或1。

實現程序必須確保對於所有的x和y而言，都存在sgn(compare(x,y))==-sgn(compare(y,x))。（這意味著當且僅當compare(y,x)拋出異常時compare(x,y)才必須拋出異常。）

實現程序還必須確保關系是可傳遞的：((compare(x,y)>0)&&(compare(y,z)>0))意味著compare(x,z)>0。

最後，實現程序必須確保compare(x,y)==0意味著對於所有的z而言，都存在sgn(compare(x,z))==sgn(compare(y,z))。

雖然這種情況很普遍，但並不嚴格要求(compare(x,y)==0)==(x.equals(y))。一般說來，任何違背這個條件的Comparator都應該清楚地指出這一事實。推薦的語言是「注意：此Comparator強行進行與equals不一致的排序。」

參數：

o1-要比較的第一個對象。

o2-要比較的第二個對象。

返回：

根據第一個參數小於、等於或大於第二個參數分別返回負整數、零或正整數。

拋出：

ClassCastException-如果參數的類型不允許此Comparator對它們進行比較。

B>booleanequals(Objectobj)指示某個其他對象是否「等於」此Comparator。此方法必須遵守Object.equals(Object)的常規協定。此外，僅當指定的對象也是一個Comparator，並且強行實施與此Comparator相同的排序時，此方法才返回true。因此，comp1.equals(comp2)意味著對於每個對象引用o1和o2而言，都存在sgn(comp1.compare(o1,o2))==sgn(comp2.compare(o1,o2))。

注意，不重寫Object.equals(Object)方法總是安全的。然而，在某些情況下，重寫此方法可以允許程序確定兩個不同的Comparator是否強行實施了相同的排序，從而提高性能。

覆蓋：

類Object中的equals

參數：

obj-要進行比較的引用對象。

返回：

僅當指定的對象也是一個Comparator，並且強行實施與此Comparator相同的排序時才返回true。

以及java.lang.Comparable

publicinterfaceComparable<T>此介面強行對實現它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的compareTo方法被稱為它的自然比較方法。

實現此介面的對象列表（和數組）可以通過Collections.sort（和Arrays.sort）進行自動排序。實現此介面的對象可以用作有序映射中的鍵或有序集合中的元素，無需指定比較器。

對於類C的每一個e1和e2來說，當且僅當e1.compareTo(e2)==0與e1.equals(e2)具有相同的boolean值時，類C的自然排序才叫做與equals一致。注意，null不是任何類的實例，即使e.equals(null)返回false，e.compareTo(null)也將拋出NullPointerException。

建議（雖然不是必需的）最好使自然排序與equals一致。這是因為在使用自然排序與equals不一致的元素（或鍵）時，沒有顯式比較器的有序集合（和有序映射表）行為表現「怪異」。尤其是，這樣的有序集合（或有序映射表）違背了根據equals方法定義的集合（或映射表）的常規協定。

例如，如果將兩個鍵a和b添加到沒有使用顯式比較器的有序集合中，使(!a.equals(b)&&a.compareTo(b)==0)，那麼第二個add操作將返回false（有序集合的大小沒有增加），因為從有序集合的角度來看，a和b是相等的。

實際上，所有實現Comparable的Java核心類都具有與equals一致的自然排序。java.math.BigDecimal是個例外，它的自然排序將值相等但精確度不同的BigDecimal對象（比如4.0和4.00）視為相等。

從數學上講，定義給定類C上自然排序的關系式如下：

{(x,y)|x.compareTo(y)<=0}。

整體排序的商是：

{(x,y)|x.compareTo(y)==0}。

它直接遵循compareTo的協定，商是C的等價關系，自然排序是C的整體排序。當說到類的自然排序與equals一致時，是指自然排序的商是由類的equals(Object)方法定義的等價關系。

{(x,y)|x.equals(y)}。

compareTo

intcompareTo(To)比較此對象與指定對象的順序。如果該對象小於、等於或大於指定對象，則分別返回負整數、零或正整數。

實現類必須確保對於所有的x和y都存在sgn(x.compareTo(y))==-sgn(y.compareTo(x))的關系。（這意味著如果y.compareTo(x)拋出一個異常，則x.compareTo(y)也要拋出一個異常。）

實現類還必須確保關系是可傳遞的：(x.compareTo(y)>0&&y.compareTo(z)>0)意味著x.compareTo(z)>0。

最後，實現者必須確保x.compareTo(y)==0意味著對於所有的z，都存在sgn(x.compareTo(z))==sgn(y.compareTo(z))。強烈推薦(x.compareTo(y)==0)==(x.equals(y))這種做法，但並不是嚴格要求這樣做。一般來說，任何實現Comparable介面和違背此條件的類都應該清楚地指出這一事實。推薦如此闡述：「注意：此類具有與equals不一致的自然排序。」

在前面的描述中，符號sgn(expression)指定signum數學函數，該函數根據expression的值是負數、零還是正數，分別返回-1、0或1中的一個值。

參數：

o-要比較的對象。

返回：

負整數、零或正整數，根據此對象是小於、等於還是大於指定對象。

拋出：

ClassCastException-如果指定對象的類型不允許它與此對象進行比較。

『叄』 二分圖最大匹配Matlab程序（在線等，感激不盡！）

第一個問題比較簡單，這里懶得對著你的圖片敲數據，用隨機數代替

long=100;

A=0.1*rand(long,1);

B=0.15*rand(long,1);

[AA BB]=meshgrid(A,B);

gg=0.5017*AA-0.65*BB;

g=gg>=-0.03&gg<=0.03; %這就是gij矩陣，相當於二分圖的連接矩陣

[num h] = maxnum(g);%第二個問題就是求二分圖的最大匹配問題，這里

%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）

以下是maxnum.m的內容，用的是匈牙利演算法

其中還用了一個遞歸的incpath函數，尋找增廣路徑

function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end

functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end

『肆』 什麼是二分圖的匹配,最大匹配,帶權最大匹配

給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配。
選擇這樣的邊數最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。
求二分圖最大匹配可以用最大流或者匈牙利演算法。

『伍』 二分圖最大匹配的Hopcroft-Carp演算法的pascal實現，求各神牛，懸賞！！！！

program hopcroft_karp;
const maxn=100;
var linkx, linky, distx, disty, queue: array[1..maxn] of longint; //link表示已經匹配的邊 x為左 y為右
map: array[1..maxn, 1..maxn] of boolean;
n, m, i, x, y, ans: longint;
function bfs: boolean;
var i, now, head, tail: longint;
begin
fillchar(distx,sizeof(distx),0); //dist表示該點在增廣路中被搜到時的距離
fillchar(disty,sizeof(disty),0);
bfs:=false;
head:=0; tail:=0;
for i:=1 to n do if (linkx[i]=0) then begin
inc(tail);
queue[tail]:=i;
end;
while (head<tail) do begin //利用隊列搜索增廣路
inc(head); now:=queue[head];
for i:=1 to n do if map[now,i] and (disty[i]=0) then begin //disty[i]<>0: 增廣路不能交叉
disty[i]:=distx[now]+1;
if (linky[i]=0) then bfs:=true
else begin //左邊的點無須判斷dist是否為0
distx[linky[i]]:=disty[i]+1;
inc(tail);
queue[tail]:=linky[i]; //queue只記錄左邊的點
end;
end;
end;
end;
function dfs(x:longint): boolean;
var i: longint;
begin
for i:=1 to n do if map[x,i] and (disty[i]=distx[x]+1) then begin //為了判斷是否能形成增廣路
disty[i]:=0; //dist改為0 防止下次再搜到此點 由於這個條件可能導致增廣路轉道
if (linky[i]=0) or dfs(linky[i]) then begin //有時候會使原來搜索到的一些增廣路無法繼續更新
linkx[x]:=i; //但是不會出現錯誤
linky[i]:=x; //DFS過程類似hungry演算法
exit(true);
end;
end;
exit(false);
end;
begin
fillchar(map,sizeof(map),false);
read(n,m);
for i:=1 to m do begin
read(x,y);
map[x,y]:=true; //map不能賦雙向值
end;
fillchar(linkx,sizeof(linkx),0);
fillchar(linky,sizeof(linky),0);
ans:=0;
while bfs do
for i:=1 to n do
if (linkx[i]=0) and dfs(i) then inc(ans);
writeln(ans);
end.
思路：首先用bfs判斷圖中是否有增廣路，如果有，則利用dist記錄下來，然後用dfs處理增廣路，不斷循環直到不存在增廣路
由於bfs一次可以判斷出許多增廣路，演算法會比hungry快很多，hungry的復雜度為n*m，而hopcroft的復雜度為n^0.5*m

『陸』 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

『柒』 二分圖匹配 匈牙利演算法

1匹配K..然後假設從M找增廣路時,找到了K點,這時LInk[k]=1..那麼再重新從1找增廣路.如果找到L，
則1與L匹配成功,M則與K匹配

『捌』 二分圖匹配（匈牙利演算法）中增廣路，交錯路的確定方式，以及什麼是增廣路

這個不畫圖講不清楚的，看書去吧，<<演算法導論>> 你得有耐心看

『玖』 問題描述： 寫出求一個二分圖的最大匹配的演算法,用c++語言

這個應該是你的作業吧，呵呵，個人建議：學習c、c++語言最好是自己動手去做，在學校的時間是寶貴的，要想做個好程序員就得在學校打好基礎，這樣工作才會有保障，這個題目應該是你的作業部分吧，盡量自己去完成吧，完成後你會發現你有很大的收獲，不僅僅是知識上的，更多的是學習樂趣和方法，作為一個過來人和你分享下個人經驗，祝你學習進步，呵呵，如果是中間出現困難了，可以和大家一起交流

『拾』 二分搜索演算法是利用什麼實現的演算法

二分搜索演算法是利用刪減實現的演算法。

二分搜索的搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。

二分搜索演算法的應用

二分搜索是一種在有序數組中查找某一特定元素的搜索演算法，這種搜索演算法每一次比較都使搜索范圍縮小一半。不過，因為有序數組的順序性，將二分搜索演算法擴展到能適用大致匹配並不是很重要。

舉例來說，二分搜索演算法可以用來計算一個賦值的排名（或稱秩，比它更小的元素的數量）、前趨（下一個最小元素）、後繼（下一個最大元素）以及最近鄰。搜索兩個值之間的元素數目的范圍查詢可以藉由兩個排名查詢（又稱秩查詢）來運行。

假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。

重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。