二分图最佳匹配基数.doc

二分图最佳匹配基数用匈牙利算法求二分图的最大匹配给定一个二分图(x,y)，x中的点和y中点的连接情况，一个匹配是二分图的子图，其中任一个x中的点只能和最多一个y中的点连接，一个y中的点也只能和一个x中的点连接，最大匹配就是使子图中的边数（我们称为匹配边）最多的匹配。mati,j记录x中的i和y中j是否可匹配，covi记录y中的已盖点i连着x中的那个点，如果i是未盖点，则covi=0，另外在寻找可增广轨时不能有重复，所以用usei记录x中的i是否被访问过。从x中一未盖点出发，通过交错轨（匹配边和非匹配边交错）找到y中的一个未盖点，然后把这条交错轨上的匹配边和非匹配边交换，则匹配边比原先多了一条，重复以上步骤直到找不到交错轨为止。伪代码如下：function can (s:byte):boolean;var i:integer;begin if uses then begin can:=false;exit; end; uses:=true; for i:=1 to n2 do if mats,i then if covi=0 then begin covi:=s; /i点变成已盖点，交换匹配边和非匹配 can:=true;exit; end else if can(covi) then begin covi:=s; /交换匹配边和非匹配边 can:=true;exit; end; can:=false;exit;end;procedure main;var i:integer;begin for i:=1 to n1 do /i肯定是未盖点 begin fillchar(use,sizeof(use),false); if can(i) then inc(sum) /sum是匹配数 end;end;没有分集合：program Project1;$APPTYPE CONSOLEuses SysUtils;const maxn=100;var graph:array1.maxn,1.maxnof boolean; matchback:array1.maxnof longint; visit:array1.maxnof boolean; rn,rm,r1,r2,ans,s:longint;function find(nowp:longint):boolean;var s:longint;begin for s:=1 to rn do if (graphnowp,s)and(not visits) then begin visits:=true; if (matchbacks=0)or(find(matchbacks) then begin matchbacks:=nowp; exit;find:=true; end; end; find:=false;end;begin WHILE not eof do begin fillchar(graph,sizeof(graph),false); fillchar(matchback,sizeof(matchback),0); readln(rn,rm); for s:=1 to rm do begin readln(r1,r2); graphr1,r2:=true; end; ans:=0; for s:=1 to rn do begin fillchar(visit,sizeof(visit),false); if find(s) then inc(ans); end; writeln(ans); end;end.分集合给关系：program URAL1109WA;$APPTYPE CONSOLEuses SysUtils;const maxn=1000;var mat:array1.maxn,1.maxnof boolean;use:array1.maxnof boolean;cov:array1.maxnof integer;var n1,n2,k,x,y,sum,i:integer;function can (s:byte):boolean;var i:integer;begin if uses then begin can:=false;exit; end; uses:=true; for i:=1 to n2 do if mats,i then if covi=0 then begin covi:=s; /i点变成已盖点，交换匹配边和非匹配 can:=true;exit; end else if can(covi) then begin covi:=s; /交换匹配边和非匹配边 can:=true;exit; end; can:=false;exit;end;procedure main;var i:integer;begin for i:=1 to n1 do /i肯定是未盖点 begin fillchar(use,sizeof(use),false); if can(i) then inc(sum) /sum是匹配数 end;end;begin while not eof do begin readln(n1,n2,k);fillchar(mat,sizeof(mat),false); for i:=1 to k do begin readln(x,y); matx,y:=true; end; fillchar(cov,sizeof(cov),0); sum:=0; main; writeln(n1+n2-sum); end;end.最小路径覆盖 2006-9-11 10:57:00 | By: Irvin 最小路径覆盖：该问题就是求一个边的集合的个数，集合满足下述条件：1 集合之中不能有相交边，却是一个通路。2 所有的集合中的边要覆盖所有的顶点。3 集合个个数最少注：求最小路径覆盖的前提是该图是有向无环图。所以answer顶点数最小覆盖的边数该问题可以转化成二分匹配来做：怎样构造二分图：1 把一个顶点i划分成两个顶点Xi和Yi2 如果顶点i到j可达，则Xi指向Yi分析：由于是有向无环图，所以每次匹配都不可能形成环，也就是不可能有两个不同的点指向同一个点，这样每加进一条边，覆盖的点数就会多一个。最大匹配数就是最小覆盖的边数。最小路径覆盖实际上可以转化为二分图来做，将要求的图中的每个结点都分成两个结点，然后分成两个集合，对与集合A中的一个点，如果与某结点有关联，那么可以将其关联到集合B中的同一点，这样就形成了一个二分图，求这个二分图的最大匹配n，这样其最小路径覆盖就是总结点数减去其最大匹配数。/JudgeOnline/problem?id=1422/happyending 1422 Accepted 60K 0MS G+ 0.86Ki nclude i nclude #define maxn 128bool conmaxnmaxn;int nV;int n;int matchmaxn;bool flagmaxn;void init()int i,j;for(i=1;i=nV;i+)for(j=i;j=nV;j+)conij=false;conji=false;bool dfs(int k)int i;for(i=1;i=nV;i+)if(flagi & conki)int t=matchi;matchi=k;flagi=false;if(t=-1|dfs(t) return true; matchi=t;return false;void max_match()int i,cnt=0;memset(match,-1,sizeof(match);for(i=1;i=nV;i+)memset(flag,true,sizeof(flag);if(dfs(i)cnt+;