Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个自己的AC的程序,0MS,但内存用了不少,其实很好改进。用模板做累死了,还是自己想。

Posted by philipfry at 2008-09-15 22:40:21 on Problem 2195
//lx ly 是顶标,这个去看看书吧。KM算法里的。
#include <iostream>
using namespace std;
#define MAXN 101
int n,m,x[MAXN][2],y[MAXN][2],lx[MAXN],ly[MAXN],g[MAXN][MAXN],xi,yi;
char map[MAXN][MAXN];
int marka[MAXN],markb[MAXN];
int mb[MAXN];
int total,al;

int find(int x){
	int j;
	marka[x]=1;
	for(j=1;j<=yi;j++)
		if(!markb[j] && (lx[x]+ly[j]==g[x][j])){
			markb[j]=1;
			if(!mb[j] || find(mb[j])){
				mb[j]=x;
				return 1;
			}
		}
	return 0;
}

int main(){
	int i,j,k;
	while(cin>>n>>m,!(n==0 && m==0)){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(ly,0,sizeof(ly));
		memset(g,0,sizeof(g));
		memset(mb,0,sizeof(mb));
		memset(map,0,sizeof(map));
		xi=yi=total=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++){
				cin>>map[i][j];
				if(map[i][j]=='m') {xi++; x[xi][0]=i; x[xi][1]=j;}
				if(map[i][j]=='H') {yi++; y[yi][0]=i; y[yi][1]=j;}
			}
		for(i=1;i<=xi;i++)
			lx[i]=0x80000000;
		for(i=1;i<=xi;i++)
			for(j=1;j<=yi;j++){
				g[i][j]=-(abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1]));
				if(lx[i]<g[i][j]) lx[i]=g[i][j];
			}
		for(i=1;i<=xi;i++){
			while(1){
				memset(marka,0,sizeof(marka));
				memset(markb,0,sizeof(markb));
				if(find(i)) break;
				al=0x7fffffff;
				for(j=1;j<=xi;j++)
					if(marka[j])
						for(k=1;k<=yi;k++)
							if(!markb[k])
								if(al>lx[j]+ly[k]-g[j][k])
									al=lx[j]+ly[k]-g[j][k];

				for(j=1;j<=xi;j++) if(marka[j]) lx[j]-=al;
				for(j=1;j<=yi;j++) if(markb[j]) ly[j]+=al;
			}
		}
		total=0;
		for(i=1;i<=yi;i++)
			total+=g[mb[i]][i];
		cout<<-total<<endl;
	}


return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator