HDU_1533 Going Home（最優匹配） 解題報告

轉載請注明出自cxb:http://blog.csdn.net/cxb569262726

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1533

說實話，這個題目剛開始還真看不出是完備匹配下的最大權匹配（當然，這個也可以用網絡流做。（應該是添加源點、匯點，源點到每個m的距離取m到所有H中最小的那個（用一個大數減掉后就是最大的）匯點到每個H的距離類似，然后求最大流） 有空再試著做一下吧，空說無益）。 我是在圖論500題里看到的，在網絡流基礎題里面。一開始想不出這個怎么流！ 后面網上查這個是二分圖最優匹配。于是昨天花幾個小時看了相關資料，寫了個比這題更水的 HDU2255。 今天寫這題的時候明顯輕松了。而且還想到用網絡流的做法。發現網絡流和二分匹配還是有聯系的。

下面直接貼代碼吧，看不懂的可以先看http://blog.csdn.net/cxb569262726/article/details/7871313：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<climits>
#define MAXN 105
using namespace std;int n,m,numm,numh;
int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN];
char s[MAXN][MAXN];
int abs(int a){return a<0?-a:a;}bool hungary(int u)
{int i;vx[u]=1;for(i=0;i<numm;i++){if(vy[i] || map[u][i]!=lx[u]+ly[i]) continue;vy[i]=1;if(matchy_x[i]==-1 || hungary(matchy_x[i])){matchy_x[i]=u;return  1;}}return 0;
}void EK_match()
{int i,j;for(i=0;i<numm;i++){int maxx=0;for(j=0;j<numh;j++)if(map[i][j]>maxx) maxx=map[i][j];lx[i]=maxx;}for(i=0;i<numm;i++){while(1){memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));if(hungary(i))break;else{int temp=INT_MAX;for(j=0;j<numm;j++) if(vx[j])for(int k=0;k<numh;k++) if(!vy[k] && temp>lx[j]+ly[k]-map[j][k])temp=lx[j]+ly[k]-map[j][k];for(j=0;j<numm;j++){if(vx[j]) lx[j]-=temp;if(vy[j]) ly[j]+=temp;}}}}
}int main()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF && (n||m)){for(i=0;i<n;i++) scanf("%s",s[i]);numm=0;for(i=0;i<n;i++){for(j=0;j<m;j++){if(s[i][j]=='m'){numh=0;for(int k=0;k<n;k++){for(int l=0;l<m;l++){if(s[k][l]=='H')map[numm][numh++]=300-(abs(i-k)+abs(j-l));}}numm++;}}}memset(matchy_x,-1,sizeof(matchy_x));EK_match();int ans=0;for(i=0;i<numm;i++)ans+=(300-map[matchy_x[i]][i]);printf("%d\n",ans);}return 0;
}

?以下是slack數組優化的：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<climits>
#define MAXN 105
using namespace std;int n,m,numm,numh;
int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN],slack[MAXN];
char s[MAXN][MAXN];
int abs(int a){return a<0?-a:a;}
int min(int a,int b) {return a<b?a:b;}bool hungary(int u)
{int i;vx[u]=1;for(i=0;i<numm;i++){if(vy[i]) continue;if(map[u][i]==lx[u]+ly[i]){vy[i]=1;if(matchy_x[i]==-1 || hungary(matchy_x[i])){matchy_x[i]=u;return  1;}}else slack[i]=min(slack[i],lx[u]+ly[i]-map[u][i]);}return 0;
}void EK_match()
{int i,j;for(i=0;i<numm;i++){int maxx=0;for(j=0;j<numh;j++)if(map[i][j]>maxx) maxx=map[i][j];lx[i]=maxx;}for(i=0;i<numm;i++){memset(slack,127,sizeof(slack));while(1){memset(vx,0,sizeof(vx));memset(vy,0,sizeof(vy));if(hungary(i))break;else{int temp=INT_MAX;for(j=0;j<numm;j++) if(!vy[j])if(temp>slack[j])   temp=slack[j];for(j=0;j<numm;j++){if(vx[j]) lx[j]-=temp;if(vy[j]) ly[j]+=temp;else slack[j]-=temp;}}}}
}int main()
{int i,j;while(scanf("%d%d",&n,&m)!=EOF && (n||m)){for(i=0;i<n;i++)scanf("%s",s[i]);numm=0;for(i=0;i<n;i++){for(j=0;j<m;j++){if(s[i][j]=='m'){numh=0;for(int k=0;k<n;k++){for(int l=0;l<m;l++){if(s[k][l]=='H')map[numm][numh++]=300-(abs(i-k)+abs(j-l));}}numm++;}}}memset(matchy_x,-1,sizeof(matchy_x));EK_match();int ans=0;for(i=0;i<numm;i++)ans+=(300-map[matchy_x[i]][i]);printf("%d\n",ans);}return 0;
}

?ok，睡覺吧。。明天比賽~~~ ?Good ? luck！