UVA1045 The Great Wall Game

题目链接：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.

",++cas,-ans);
	}
	return 0;
}