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