数模,算法模板

1、令g=（x,*,y）是一个二分图，其中.令m为g中的任意匹配1。将令g=（x,*,y）是一个二分图，其中.令m为g中的任意匹配1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到22。如果在上一步没有新的标记加到x转3。当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，转44。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转55。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如bfs过

2、程bool map100300; (-(-(-(-if(previ2=- dfs 实现过程 dfs 实现过程#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;在主程序中调用下面的程序Bmatch := 0; For(i=1t;in;i+)Bmatch:= Bmatch+ 出最大匹配数KM 算法和最大匹配（匈牙利算法匈牙利算法的分析与运用匈牙利算法的精髓在于 USED 哈希数组的使用，下面是匈牙利算法的主要模functionfind(x:long ;forj:=1tof(linex

4、,j)and(notusedj)if(mmj=0)or(find(mmj)thene在原程序进行调用是也就是简简单单的一句话fori:=1tondobeginfillchar(used,sizeof(used),0);iffind(i)then注意这里：每一次找匹配时 USED 都是清0 的，这是为什么可以找USD “新欢”中最好的。匈牙利算法解题是极为简单的，但是图论的难并不是难在解答，而是建图过程，也难怪会有牛曰：用匈牙利算法，建图是痛苦的，最后的。当然这些！也只能搞搞NOIP 了，一般不会太难，所以此算法，极KM算法最大流的 KM 算法，又KM算法最大流的 KM 算法，又算的上算法世界中

5、的一多奇葩了，下面是KM 算法的functionfind(x:byte): fory:=1tondo;ifnotvyyand(lxx+lyy=wx,y)thenbegin if(aimy=0)orfind(aimy)thenbegin 可以见出，该模块与匈牙利算法极为相似，差别便是ifnotvyyandlxx+lyy=wx,y) 判断语句了，这里涉及到KM算法的但是在源程序的调用过程更是烦杂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 |=