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

最小费用最大流为什么TLE???

Posted by yanqing at 2011-05-04 21:11:13 on Problem 2195
大牛来帮忙!!

#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:
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