二分圖最佳匹配基數(shù)

1、二分圖最佳匹配基數(shù)用匈牙利算法求二分圖的最大匹配給定一個二分圖(x,y)，x中的點和y中點的連接情況，一個匹配是二分圖的子圖，其中任一個x中的點只能和最多一個y中的點連接，一個y中的點也只能和一個x中的點連接，最大匹配就是使子圖中的邊數(shù)（我們稱為匹配邊）最多的匹配。mati,j記錄x中的i和y中j是否可匹配，covi記錄y中的已蓋點i連著x中的那個點，如果i是未蓋點，則covi=0，另外在尋找可增廣軌時不能有重復(fù)，所以用usei記錄x中的i是否被訪問過。從x中一未蓋點出發(fā)，通過交錯軌（匹配邊和非匹配邊交錯）找到y(tǒng)中的一個未蓋點，然后把這條交錯軌上的匹配邊和非匹配邊交換，則匹配邊比原先多了一條，

2、重復(fù)以上步驟直到找不到交錯軌為止。偽代碼如下：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; c

3、an:=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是匹配數(shù) end;end;沒有分集合：program Project1;$APPTYPE CONSOLEuses SysUtils;const maxn=100;var graph:array1.maxn,1.maxnof boolean; matchback:array1.maxnof longint

4、; 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;beg

5、in 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;e

6、nd.分集合給關(guān)系：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

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

8、 then inc(sum) /sum是匹配數(shù) 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  最小路徑覆蓋：該問題就是求一

9、個邊的集合的個數(shù)，集合滿足下述條件：1 集合之中不能有相交邊，卻是一個通路。2 所有的集合中的邊要覆蓋所有的頂點。3 集合個個數(shù)最少注：求最小路徑覆蓋的前提是該圖是有向無環(huán)圖。所以answer頂點數(shù)最小覆蓋的邊數(shù)該問題可以轉(zhuǎn)化成二分匹配來做：怎樣構(gòu)造二分圖：1 把一個頂點i劃分成兩個頂點Xi和Yi2 如果頂點i到j(luò)可達(dá)，則Xi指向Yi分析：由于是有向無環(huán)圖，所以每次匹配都不可能形成環(huán)，也就是不可能有兩個不同的點指向同一個點，這樣每加進(jìn)一條邊，覆蓋的點數(shù)就會多一個。最大匹配數(shù)就是最小覆蓋的邊數(shù)。最小路徑覆蓋實際上可以轉(zhuǎn)化為二分圖來做，將要求的圖中的每個結(jié)點都分成兩個結(jié)點，然后分成兩個集合，對與集

10、合A中的一個點，如果與某結(jié)點有關(guān)聯(lián)，那么可以將其關(guān)聯(lián)到集合B中的同一點，這樣就形成了一個二分圖，求這個二分圖的最大匹配n，這樣其最小路徑覆蓋就是總結(jié)點數(shù)減去其最大匹配數(shù)。/happyending 1422 Accepted 60K 0MS G+ 0.86Ki nclude <stdio.h>i nclude <string.h>#define maxn 128bool conmaxnmaxn;int nV;int n;int matchmaxn;bool flagmaxn;void init() int i,j; for(i=1;i<=nV;i

11、+)  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; 

12、60; 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+;  printf("%dn",nV-cnt);int main() int ncase,i,t1,t2; scanf("%d",&ncase); while(ncase-)  scanf("%dn%d",&nV,&n