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 |
Re:为什么俺的最小费用最大流会TLE啊?In Reply To:为什么俺的最小费用最大流会TLE啊? Posted by:HeartRush at 2007-09-14 00:15:16 > > #include<stdio.h> > #include<string.h> > #include<math.h> > #define maxint 0x7fffffff > #define maxn 52 > #define size 2*maxn > > int need[maxn][maxn]; > int provide[maxn][maxn]; > int cost[maxn][maxn][maxn]; > > int cap[size][size]; > int flow[size][size]; > int pre[size]; > int w[size][size]; > int d[size]; > > int n,m,k; > int S,T; > int min; > int max_flow; > int N; > > int Bellman_ford() > { > int i,j,k; > memset(pre,0,sizeof(pre)); > for(i=1;i<=N;i++) > d[i]=maxint; > d[0]=0; > for(k=1;k<=N;k++) > for(i=0;i<=N;i++) > for(j=0;j<=N;j++) > if(cap[i][j]-flow[i][j]>0) > if(d[i]<maxint && d[j]>d[i]+w[i][j]){ > d[j]=d[i]+w[i][j]; > pre[j]=i; > } > if(pre[T]!=0) > return 1; > else > return 0; > } > > int Edmonds_Karp() > { > int cp,v; > int ans=0; > max_flow=0; > while(Bellman_ford()) > { > cp=maxint; > for(v=T;v!=S;v=pre[v]) > if(cp>cap[pre[v]][v]-flow[pre[v]][v]) > cp=cap[pre[v]][v]-flow[pre[v]][v]; > for(v=T;v!=S;v=pre[v]) > { > flow[pre[v]][v]+=cp; > flow[v][pre[v]]=-flow[pre[v]][v]; > ans+=cp*w[pre[v]][v]; > } > max_flow+=cp; > } > return ans; > } > int main() > { > //freopen("f.in","r",stdin); > int i,j,t,sum; > for(;;) > { > scanf("%d%d%d",&n,&m,&k); > if(n==0 && m==0 && k==0) > break; > for(i=1;i<=n;i++) > for(j=1;j<=k;j++) > scanf("%d",&need[i][j]); > for(i=1;i<=m;i++) > for(j=1;j<=k;j++) > scanf("%d",&provide[i][j]); > for(t=1;t<=k;t++) > for(i=1;i<=n;i++) > for(j=1;j<=m;j++) > scanf("%d",&cost[t][i][j]); > min=0; > for(t=1;t<=k;t++) > { > memset(flow,0,sizeof(flow)); > memset(cap,0,sizeof(cap)); > memset(w,0,sizeof(w)); > S=0,T=m+n+1,N=m+n+1; > for(i=1;i<=m;i++) > cap[S][i]=provide[i][t]; > for(i=1;i<=m;i++) > for(j=m+1;j<=m+n;j++) > cap[i][j]=maxint; > for(i=m+1;i<=m+n;i++) > cap[i][T]=need[i-m][t]; > for(i=1;i<=m;i++) > for(j=m+1;j<=m+n;j++) > { w[i][j]=cost[t][j-m][i]; > w[j][i]=-w[i][j];} > min+=Edmonds_Karp(); > for(i=1,sum=0;i<=n;i++) > sum+=need[i][t]; > if(max_flow!=sum) > break; > } > if(t>k) > printf("%d\n",min); > else > printf("-1\n"); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator