題意:在一個n*n的棋盤上有n個棋子，要求通過移動棋子使棋子的排布滿足以下情況之一：呈橫行排列；呈縱行排列；呈對角線排列(有兩條)。

棋子移動一個單元格的費用為1，總費用為所有棋子的移動費用之和。求最小費用。

分析:因為這題的數據很小,故可以枚舉每種情況.對于每種情況,我們可以用二分匹配的方法算出最小費用(對于每個棋子,連接n條邊到n個目標位置,權值設為負,這樣最佳二分匹配求的最大值就是答案的最小值了);

// File Name: 1045.cpp // Author: Zlbing // Created Time: 2013/4/20 15:58:22 #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #include<cstdio> #include<set> #include<map> #include<vector> #include<cstring> #include<stack> #include<cmath> #include<queue> using namespace std; #define CL(x,v); memset(x,v,sizeof(x)); #define INF 1000000000 #define LL long long #define REP(i,r,n) for(int i=r;i<=n;i++) #define RREP(i,n,r) for(int i=n;i>=r;i--) const int MAXN=20; int X[MAXN],Y[MAXN]; int Left[MAXN]; int w[MAXN][MAXN]; int Lx[MAXN],Ly[MAXN]; bool S[MAXN],T[MAXN]; int N; bool match(int i) {S[i]=true;for(int j=1;j<=N;j++)if(Lx[i]+Ly[j]==w[i][j]&&!T[j]){T[j]=true;if(Left[j]==0||match(Left[j])){Left[j]=i;return true;}}return false; } void update(){int a=INF;for(int i=1;i<=N;i++)if(S[i])for(int j=1;j<=N;j++)if(!T[j])a=min(a,Lx[i]+Ly[j]-w[i][j]);for(int i=1;i<=N;i++){if(S[i])Lx[i]-=a;if(T[i])Ly[i]+=a;} } void KM() {for(int i=1;i<=N;i++){Left[i]=Lx[i]=Ly[i]=0;for(int j=1;j<=N;j++){Lx[i]=max(Lx[i],w[i][j]);}}for(int i=1;i<=N;i++){for(;;){CL(S,0);CL(T,0);if(match(i))break;else update();}} }int main() {int cas=0; while(~scanf("%d",&N)){if(N==0)break;REP(i,1,N){int a,b;scanf("%d%d",&a,&b);X[i]=a;Y[i]=b;}int ans=INF;REP(i,1,N){REP(k,1,N)REP(j,1,N){int dist=abs(X[k]-i)+abs(Y[k]-j);w[k][j]=-dist;}KM();int minn=0;REP(i,1,N){minn+=-w[Left[i]][i];}ans=min(ans,minn);}REP(i,1,N) {REP(k,1,N)REP(j,1,N){int dist=abs(X[k]-j)+abs(Y[k]-i);w[k][j]=-dist;}KM();int minn=0;REP(i,1,N)minn+=-w[Left[i]][i];ans=min(ans,minn);}REP(k,1,N)REP(i,1,N){int dist=abs(X[k]-i)+abs(Y[k]-i);w[k][i]=-dist;}KM();int minn=0;REP(i,1,N)minn+=-w[Left[i]][i];ans=min(ans,minn);REP(k,1,N)REP(i,1,N){int dist=abs(X[k]-i)+abs(Y[k]-N+i-1);w[k][i]=-dist;}KM();minn=0;REP(i,1,N)minn+=-w[Left[i]][i];ans=min(ans,minn);printf("Board %d: %d moves required.\n\n",++cas,ans);}return 0; }

?

轉載于:https://www.cnblogs.com/arbitrary/archive/2013/04/21/3033852.html

總結

以上是生活随笔為你收集整理的UVA-1045 - The Great Wall Game(二分图最佳匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。