二分圖最佳完美匹配

2019-11-11 00:59:51

字體：大中小

供稿：網(wǎng)友

最佳完美匹配即權(quán)值和最大的完美匹配，這里運(yùn)用到KM算法。引進(jìn)兩個(gè)概念： 1、可行頂標(biāo)，為一個(gè)節(jié)點(diǎn)函數(shù)l，使任意邊（u，v）均滿足l(u)+l(v)>=w(u,v); 2、相等子圖,為原圖的一個(gè)生成子圖，包含所有點(diǎn)以及滿足l(u)+l(v)=w(u,v)的邊。 定理：如相等子圖G’有完美匹配，則該匹配即為所求。 證明：G’的權(quán)值和為所有頂點(diǎn)的頂標(biāo)和Sum，而此時(shí)原圖G任意一個(gè)完美匹配的權(quán)值和均<=Sum。 算法流程： 1.構(gòu)造一個(gè)可行頂標(biāo)（一般可令lx（u）為與u相連的邊的最大權(quán)值，ly（v）=0）； 2.搜索尋找增廣路，如找到換下一個(gè)節(jié)點(diǎn)，否則轉(zhuǎn)3； 3.設(shè)X為搜索中左邊已訪問(wèn)的點(diǎn)，Y為右邊已訪問(wèn)的點(diǎn)，令路M(搜索失敗)上所有邊，在X中的頂標(biāo)減去d，在Y中的頂標(biāo)加上d， d為min{l(x)+l(y)-w(x,y)},x屬于X,y不屬于Y。下面說(shuō)明一下為什么這樣選取d：如果比d小不能保證有新邊加入，而大于d會(huì)頂標(biāo)變得不可行，破壞性質(zhì)。

4.調(diào)整后l繼續(xù)執(zhí)行2；

時(shí)間O(n^4)如果加一個(gè)小優(yōu)化，在計(jì)算d時(shí)用一個(gè)數(shù)組slack[v]（v不屬于Y）來(lái)維護(hù)與v相連的邊min{lx(u)+ly(v)-w(u,v)}可降下一個(gè)n。來(lái)道板子POJ3565

這里寫圖片描述為什么上面的A了，下面的WA？（窩調(diào)了一天QAQ）

#include <cstdio>#include <algorithm>#include <cstring>#define maxn 1005#define eps 1e-10#define INF 0x3f3f3f3f#include <cmath>int n,m,match[maxn],head[maxn],vis[maxn],visy[maxn];using namespace std;double d,slack[maxn],lx[maxn],ly[maxn],x[maxn],y[maxn],p,q;struct xx{ int v,next; double q;}b[maxn*maxn*2];void add(int u,int v,double q){ b[++m]=(xx){v,head[u],q}; head[u]=m;}int find(int t){ vis[t]=1; for (int k=head[t];k!=0;k=b[k].next) { int v=b[k].v; double g=lx[t]+ly[v]-b[k].q; if (visy[v]) continue; if (abs(g)<=eps)//該邊可行 { visy[v]=1; if (!match[v]||find(match[v])) { match[v]=t; return true; } }else slack[v]=min(slack[v],g);//t在X中且v不在Y中 } return false;}void km(){ memset(match,0,sizeof(match)); //memset(ly,0,sizeof(ly)); for (int i=1;i<=n;i++) ly[i]=0; for (int i=1;i<=n;i++) { lx[i]=-INF; for (int k=head[i];k!=0;k=b[k].next) lx[i]=max(lx[i],b[k].q); } for (int i=1;i<=n;i++) { //memset(slack,INF,sizeof(slack)); for (int j=1;j<=n;j++) slack[j]=INF; for (;;) { memset(vis,0,sizeof(vis)); memset(visy,0,sizeof(visy)); if (find(i)) break;//找到增廣路 d=INF; //調(diào)整lx和ly for (int j=1;j<=n;j++) if (!visy[j]) d=min(d,slack[j]); for (int j=1;j<=n;j++){ if (vis[j]) lx[j]-=d;//在X中 } for (int j=1;j<=n;j++){ if (visy[j]) ly[j]+=d;//在Y中 else slack[j]-=d; //不在Y中則維護(hù)slack } } } return ;}int main(){ while (scanf("%d",&n)==1) { m=0; memset(head,0,sizeof(head)); for (int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); for (int i=1;i<=n;i++){ scanf("%lf%lf",&p,&q); for (int j=1;j<=n;j++){ double dis=sqrt((x[j]-p)*(x[j]-p)+(y[j]-q)*(y[j]-q));//?????? add(j,i,-dis);//add(i,j,-dis); } } km(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (match[j]==i) {