| ||||||||||
| 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 | |||||||||
最小费用最大流为什么TLE???大牛来帮忙!!
#include <cstdio>
#include <cstring>
int n,m;
int tot;
int o;
int to[20000];
int op[20000];
int next[20000];
int k[1000];
int cur[50000];
int value[50000];
int hx[1010],hy[1010];
int mx[1010],my[1010];
int a[600][600];
int f[100000];
int d[1010];
bool v[1010];
int min(int a,int b){
if (a>b) return b;else return a;
}
void add(int a,int b,int c,int d){
to[++tot]=b;
value[tot]=c;
cur[tot]=d;
next[tot]=k[a];
k[a]=tot;
op[tot]=tot+1;
to[++tot]=a;
value[tot]=-c;
cur[tot]=0;
next[tot]=k[b];
k[b]=tot;
op[tot]=tot-1;
}
int cal(int i,int j){
int x=hx[i]-mx[j];
int y=hy[i]-my[j];
if (x<0) x=-x;
if (y<0) y=-y;
return x+y;
}
int pren[500],pret[500];
void spfa(){
memset(pren,-1,sizeof(pren));
memset(pret,0,sizeof(pret));
memset(d,63,sizeof(d));
memset(v,0,sizeof(v));
d[0]=0;
v[0]=true;
int head=0,tail=1;
while (head<tail){
int x=f[++head];
v[x]=false;
for (int t=k[x];t;t=next[t]){
int y=to[t];
if (cur[t] && d[y]>d[x]+value[t]){
pren[y]=x;
pret[y]=t;
d[y]=d[x]+value[t];
v[y]=true;
f[++tail]=y;
}
}
}
}
int main(){
while (1)
{
scanf("%d%d\n",&n,&m);
if (n==0 && m==0) break;
o=0;tot=0;
hx[0]=hy[0]=mx[0]=my[0]=0;
memset(next,0,sizeof(next));
memset(k,0,sizeof(k));
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
char c;
scanf("%c",&c);
if (c=='H') {hx[++hx[0]]=i;hy[++hy[0]]=j;}
else if (c=='m') {mx[++mx[0]]=i;my[++my[0]]=j;}
}
scanf("\n");
}
o=2*hx[0]+1;
for (int i=1;i<=hx[0];i++)
for (int j=1;j<=mx[0];j++)
add(i,j+hx[0],cal(i,j),1);
for (int i=1;i<=hx[0];i++) add(0,i,0,1);
for (int i=1;i<=hx[0];i++) add(i+hx[0],o,0,1);
int flow=0,ans=0;
while (flow!=hx[0]){
spfa();
if (d[o]>5000000 || pren[o]==-1 || d[o]==0) break;
ans+=d[o];
flow++;
int x=pren[o],y=pret[o];
while (x!=-1){
cur[y]--;
cur[op[y]]++;
y=pret[x];
x=pren[x];
}
}
printf("%d\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator