如果一个可行顶标使得原图的相等子图中存在完美匹配

1、首先,如果一个可行顶标使得原图的相等子图中存在完美匹配,那么这个完美匹配一定是最优解.然后只要证一定存在一组可行顶标,使得原图的相等子图中存在完美匹配.只须证:可以通过改进可行顶标使相等子图中存在完美匹配.如果现在的相等子图中不存在完美匹配且无增广路,则匈牙利树中的节点可以分为4类.S,T,S,T.那么在相等子图中，T中一定存在未盖点,T到S中无匹配边,S到T中无边.我们现在考虑如何使相等子图产生一条增广路.方法是:向匈牙利树中加点.因为一旦加入,在未找到增广路前,不会删掉,那么不再匈牙利树中的点的数目在严格减小,一定有一次加入了那个未盖点,增广路就找到了.那么如何加点呢?用T加S中的？无匹配

2、边啊！用S加T中的！怎么改？一定是dec(l(x),d)(xeS)d=minl(x)+l(y)一w(x,y)IxeS,yeT使加一条从s到T的边，也保证s到T的顶标可行.为了保证S到T的顶标可行，且匹配边不作改变,inc(l(y),d)(yeT)由于增加了T的顶标，所以T到T的顶标可行.这样修改后是否会导致有些匹配边不再是匹配边呢？不会，因为匹配边只出现在S到T,S到T,而他们的l(x)+l(y)不变.这样，尝试从X中的一个未盖点k找到增广路，至多改n次可行顶标(每次至少增加1个Y中的点到匈牙利树中)，为了保证总时间复杂度为O(n3),必须使找d的时间复杂度降到O(n).为此，我们定以slac

3、k(y)=minl(x)+l(y)w(x,y)IxeS,yeT.在扩展匈牙利树的时候更新，在修改可行顶标前,d=minslack(y)IyeT,修改以后，只需要dec(slack(y),d)就行了.总的时间复杂度如何呢？第k次要找到从k出发的一条增广路.找的全程中，扩展匈牙利树是O(n2)的，至多更改n次可行顶标，更改的复杂度是O(n)的，所以找一条增广路的过程中,改可行顶标的时间复杂度也是O(n2)的.因为要执行n次找增广路的过程，所以总的时间复杂度就是O(n3)的.Code:constmaxn=500;maxk=10000;typeinteger=longint;varn,k,yy:int

4、eger;w:array1.maxn,1.maxnofinteger;slack,who,lx,ly:array1.maxnofinteger;(*whoy记录x对应的匹配点y,x=minl(x)+l(y)-w(x,y)=slack(y)IxeS*)(*lx记录点集X的顶标，ly记录点集Y的可行顶标*)link:arrayl.maxn+1ofinteger;/记录点集Y的匹配边x,=0说明没有vx:arrayl.maxnofboolean;/x是否在匈牙利树中fa:arrayl.maxnofinteger;/把y加进匈牙利树的x的对应的匹配点fin,fout:text;procedurerea

5、ddata;vari,a,b:integer;beginreadln(fin,n,k);fori:=1tokdobeginread(fin,a,b);readln(fin,wa,b);end;end;functionfind(u,father:integer):integer;/如果有增广路,返回终点,否则是0vari,t:integer;beginvxu:=true;/进入了匈牙利树fori:=1tondoiffai=0thenbegin/Y中的i还没有进入匈牙利树t:=lxu+lyi-wu,i;ift=0thenbegin/相等子图中有这条边fai:=father;/设置faiiflink

6、i=0thenbegin/找到未盖点,找到增广路find:=i;exit;end;t:=find(linki,i);ift0thenbeginfind:=t;exit;end;endelseiftlxithenlxi:=wi,j;/初始可行顶标fork:=1tondobeginfillchar(vx,sizeof(vx),0);fillchar(fa,sizeof(fa),0);fori:=1tondoslacki:=maxlongint;/初始化linkyy:=k;/设置yy与k匹配ep:=find(k,yy);whileep=0dobegin/没有找到增广路d:=maxlongint;fo

7、ri:=1tondoif(fai=0)and(dslacki)thend:=slacki;/求出dfori:=1tondoifvxithendec(lxi,d);/修改S中的点的顶标fori:=1tondoiffai=0thendec(slacki,d)/更新slackelseinc(lyi,d);/修改T中的点的顶标fori:=1tondoif(fai=0)and(slacki=0)thenbeginfai:=whoi;iflinki=0thenbegin/找到增广路ep:=i;break;endelsebegin/扩展匈牙利树ep:=find(linki,i);ifep0thenbreak;/如果找到增广路end;end;end;whileepyydobeginlinkep:=linkfaep;ep:=faep;end;end;end;procedureprint;vari:integer;sum:integer;beginsum:=0;fori:=1tondoinc(sum,lxi+lyi);writeln(fout,sum