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