數(shù)模,算法模板

1、令g=（x,*,y）是一個(gè)二分圖，其中.令m為g中的任意匹配1。將令g=（x,*,y）是一個(gè)二分圖，其中.令m為g中的任意匹配1。將x的所有不與m的邊關(guān)聯(lián)的頂點(diǎn)表上￥，并稱所有的頂點(diǎn)為未掃描的。轉(zhuǎn)到22。如果在上一步?jīng)]有新的標(biāo)記加到x轉(zhuǎn)3。當(dāng)存在x被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，選擇一個(gè)被標(biāo)記但未被掃描的x的頂點(diǎn)，比如xi，用（xi）記y 的所有頂點(diǎn)，這些頂點(diǎn)被不屬于m且尚未標(biāo)記的邊連到xi現(xiàn)在頂點(diǎn)xi 是被掃描的。如果不存在被標(biāo)記但未被掃描的頂點(diǎn)，轉(zhuǎn)44。如果在步驟3沒(méi)有新的標(biāo)記被標(biāo)記到y(tǒng)的頂點(diǎn)上，則停，否則轉(zhuǎn)55。當(dāng)存在y被標(biāo)記但未被掃描的頂點(diǎn)時(shí)。選擇y的一個(gè)被標(biāo)記但未被掃描的頂點(diǎn)，比如bfs過(guò)

2、程bool map100300; (-(-(-(-if(previ2=- dfs 實(shí)現(xiàn)過(guò)程 dfs 實(shí)現(xiàn)過(guò)程#define MAX 100bool mapMAXMAX,searchedMAX; bool return true; return (-(-程：Function find(var st,sf,i,j,t;queue,father:array1.100of queue1:=k;st:=1;sf:=forif(fatheri=0&aqueuest,i=1) if match2i0 thenqueuesf:=match2i; fatheri := queuest; end elsej:=q

3、ueuest; while true dot:=match1j:=match2i:=if t = 0 then break; i:=t;j:=fathert;t:=match1j:=match2i:=if t = 0 then break; i:=t;j:=fathert;在主程序中調(diào)用下面的程序Bmatch := 0; For(i=1t;in;i+)Bmatch:= Bmatch+ 出最大匹配數(shù)KM 算法和最大匹配（匈牙利算法匈牙利算法的分析與運(yùn)用匈牙利算法的精髓在于 USED 哈希數(shù)組的使用，下面是匈牙利算法的主要模functionfind(x:long ;forj:=1tof(linex

4、,j)and(notusedj)if(mmj=0)or(find(mmj)thene在原程序進(jìn)行調(diào)用是也就是簡(jiǎn)簡(jiǎn)單單的一句話fori:=1tondobeginfillchar(used,sizeof(used),0);iffind(i)then注意這里：每一次找匹配時(shí) USED 都是清0 的，這是為什么可以找USD “新歡”中最好的。匈牙利算法解題是極為簡(jiǎn)單的，但是圖論的難并不是難在解答，而是建圖過(guò)程，也難怪會(huì)有牛曰：用匈牙利算法，建圖是痛苦的，最后的。當(dāng)然這些！也只能搞搞NOIP 了，一般不會(huì)太難，所以此算法，極KM算法最大流的 KM 算法，又KM算法最大流的 KM 算法，又算的上算法世界中

5、的一多奇葩了，下面是KM 算法的functionfind(x:byte): fory:=1tondo;ifnotvyyand(lxx+lyy=wx,y)thenbegin if(aimy=0)orfind(aimy)thenbegin 可以見(jiàn)出，該模塊與匈牙利算法極為相似，差別便是ifnotvyyandlxx+lyy=wx,y) 判斷語(yǔ)句了，這里涉及到KM算法的但是在源程序的調(diào)用過(guò)程更是煩雜fork:=1ton，iffind(k)thenbreak; fori:=1tondo if vxi thenforj:=1tonifnotvyjiflxi+lyj-wi,j bool ,s = = =hdoj_1150 匈牙利算using namespaboolmark1100,mark2100; bool ,s = = =-1|= returnreturnvoid;bool flog = false; if(listvij=-mark1i=false; listvij = i; if(i=0)flog= )= )= -1 |=