| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为什么会超时,搞不懂#include<iostream>
using namespace std;
struct point
{
int x,y;
};
point p1[1005],p2[1005];
const int N=1005;
const int inf=999999;
int x[N],y[N];
int mx[N],my[N];
int map[N][N];
int lx[N],ly[N];
int slack[N];
int n;
bool dfs(int v)
{
int j;
x[v]=1;
for(j=0;j<n;j++)
{
int wt=lx[v]+ly[j]-map[v][j];
if(!y[j]&& wt==0)
{
y[j]=1;
if(my[j]== -1||dfs(my[j]))
{
my[j]=v;//mx[v]=j;
return true;
}
}
else if(slack[j]>-wt) slack[j]=-wt;
}
return false;
}
int perfect_match(int n)
{
int i,j,k;
for(i=0;i<n;i++)
{
my[i]=-1;
lx[i]=inf;ly[i]=0;
for(j=0;j<n;j++)
{
if(lx[i]>map[i][j]) lx[i]=map[i][j];
}
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++) x[i]=0,y[i]=0,slack[i]=inf;
while(!dfs(k))
{
int ans;
//printf("ans=%d\n",ans);
int d=inf;
for(i=0;i<n;i++)
{
if(!y[i]&&slack[i]<d) d=slack[i];
}
for(i=0;i<n;i++)
{
if(x[i]) {lx[i]+=d;}
if(y[i]) {ly[i]-=d;}
else slack[i]-=d;
}
}
}
int ans=0;
for(i=0;i<n;i++)
ans+=lx[i]+ly[i];
return ans;
}
int main()
{
int m;
int i,j,k,l;
char a;
while(scanf("%d%d",&n,&m)!=EOF)
{
k=0;l=0;
if(n==0 && m==0) break;
for(i=0;i<n;i++)
{
getchar();
for(j=0;j<m;j++)
{
scanf("%c",&a);
if(a=='m')
p1[l].x=i,p1[l++].y=j;
if(a=='H')
p2[k].x=i,p2[k++].y=j;
}
}
for(i=0;i<=l;i++)
for(j=0;j<=k;j++)
{
map[i][j]=(abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y));
}
printf("%d\n",perfect_match(l));
}
// system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator