UVA1045 The Great Wall Game

约定不等于承诺〃 2023-08-17 15:35 127阅读 0赞

题目链接：[UVA1045 The Great Wall Game][]  
题目大意：在一个n\*n的棋盘上有n个棋子，要求通过移动棋子使棋子的排布满足以下情况之一：呈横行排列；呈纵行排列；呈对角线排列(有两条)。  
题解：这一道题的最终状态很少，所以我们可以枚举最终的结束状态，然后再计算，至于怎么计算，可以用最大流最小割，也可以用二分图完美匹配，我用的是后者。  
代码：

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    using namespace std;
    const int MAXNODE = 105;
    typedef int Type;
    const Type INF=0x3f3f3f3f;
    struct KM{
        int n;
        Type g[MAXNODE][MAXNODE];
        Type Lx[MAXNODE],Ly[MAXNODE],slack[MAXNODE];
        int left[MAXNODE];
        bool S[MAXNODE],T[MAXNODE];
        void init(int n){
            this->n=n;
        }
        void add_Edge(int u,int v,Type val){
            g[u][v]=val;
        }
        bool dfs(int i){
            S[i]=1;
            for(int j=0;j<n;j++){
                if(T[j]){
                    continue;
                }
                Type tmp=Lx[i]+Ly[j]-g[i][j];
                if(!tmp){
                    T[j]=1;
                    if(left[j]==-1||dfs(left[j])){
                        left[j]=i;
                        return 1;
                    }
                }
                else{
                    slack[j]=min(slack[j],tmp);
                }
            }
            return 0;
        }
        void update(){
            Type a=INF;
            for(int i=0;i<n;i++){
                if(!T[i]){
                    a=min(a,slack[i]);
                }
            }
            for(int i=0;i<n;i++){
                if(S[i]){
                    Lx[i]-=a;
                }
                if(T[i]){
                    Ly[i]+=a;
                }
            }
        }
        Type km(){
            for(int i=0;i<n;i++){
                left[i]=-1;
                Lx[i]=-INF;
                Ly[i]=0;
                for(int j=0;j<n;j++){
                    Lx[i]=max(Lx[i],g[i][j]);
                }
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    slack[j]=INF;
                }
                while(1){
                    for(int j=0;j<n;j++){
                        S[j]=T[j]=0;
                    }
                    if(dfs(i)){
                        break;
                    }
                    else{
                        update();
                    }
                }
            }
            Type ans=0;
            for (int i=0;i<n;i++){
                ans+=g[left[i]][i];
            }
            return ans;
        }
    }gao;
    const int N=20;
    int n,x[N],y[N];
    int dis(int x1,int y1,int x2,int y2){
        return abs(x1-x2)+abs(y1-y2);
    }
    int main(){
        int cas=0;
        while(~scanf("%d",&n)&&n){
            gao.init(n);
            for(int i=0;i<n;i++){
                scanf("%d%d",&x[i],&y[i]);
                x[i]--;
                y[i]--;
            }
            int ans=-1000;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    for(int k=0;k<n;k++){
                        gao.add_Edge(j,k,-dis(x[j],y[j],i,k));
                    }
                }
                ans=max(ans,gao.km());
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    for(int k=0;k<n;k++){
                        gao.add_Edge(j,k,-dis(x[j],y[j],k,i));
                    }
                }
                ans=max(ans,gao.km());
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    gao.add_Edge(i,j,-dis(x[i],y[i],j,j));
                }
            }
            ans=max(ans,gao.km());
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    gao.add_Edge(i,j,-dis(x[i],y[i],n-j-1,j));
                }
            }
            ans=max(ans,gao.km());
            printf("Board %d: %d moves required.\n\n",++cas,-ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/withhope/p/11291667.html

[UVA1045 The Great Wall Game]: https://cn.vjudge.net/problem/UVA-1045