二分匹配算法

‘壹’ 详细讲解二分图匹配中的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++语言最好是自己动手去做，在学校的时间是宝贵的，要想做个好程序员就得在学校打好基础，这样工作才会有保障，这个题目应该是你的作业部分吧，尽量自己去完成吧，完成后你会发现你有很大的收获，不仅仅是知识上的，更多的是学习乐趣和方法，作为一个过来人和你分享下个人经验，祝你学习进步，呵呵，如果是中间出现困难了，可以和大家一起交流

‘拾’ 二分搜索算法是利用什么实现的算法

二分搜索算法是利用删减实现的算法。

二分搜索的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

二分搜索算法的应用

二分搜索是一种在有序数组中查找某一特定元素的搜索算法，这种搜索算法每一次比较都使搜索范围缩小一半。不过，因为有序数组的顺序性，将二分搜索算法扩展到能适用大致匹配并不是很重要。

举例来说，二分搜索算法可以用来计算一个赋值的排名（或称秩，比它更小的元素的数量）、前趋（下一个最小元素）、后继（下一个最大元素）以及最近邻。搜索两个值之间的元素数目的范围查询可以借由两个排名查询（又称秩查询）来运行。

假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。