二分圖最佳完美匹配

2019-11-10 21:42:05

字體：大中小

來源：轉載

供稿：網友

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

4.調整后l繼續執行2；

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

這里寫圖片描述為什么上面的A了，下面的WA？（窩調了一天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; //調整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中則維護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) {