> #include<iostream>
> using namespace std;
> const int maxs=INT_MAX/10;
> int n,m,k,sum,len;
> int supply[120][60];
> int stock[120][60];
> bool visit[120],flat;
> int u,c[120],pre[120],f[120];
> struct{
>       int cost,c;
>       int f,rf;
> }num[120][120];
> int mins(int a,int b){ return a<b?a:b; }
> int feiyong(int t){
>        for(int i=1;i<len;i++){
>            visit[i]=0;
>            c[i]=num[0][i].cost;
>            f[i]=num[0][i].f;
>            pre[i]=0; 
>        }
>        visit[0]=1;pre[0]=-1;
>        while(true){
>           int min=maxs;
>           for(int j=1;j<len;j++)
>                if(visit[j]==0 && c[j]<min){   
>                   min=c[j];
>                   u=j;   
>                }
>           if(min==maxs) return min;
>           visit[u]=1;
>           if(u==len-1){
>              int w1=pre[u],w2=u;
>              while(w1!=-1){
>                  if(num[w1][w2].rf>0){
>                          num[w1][w2].rf=num[w1][w2].rf-f[u];
>                          supply[w2][t]+=f[u];
>                          stock[w1][t]+=f[u];
>                  }
>                  else{
>                      if(w1!=0 && w2!=len-1){
>                            num[w2][w1].rf=num[w2][w1].rf+f[u]; 
>                            supply[w1][t]-=f[u];
>                            stock[w2][t]-=f[u];
>                      }
>                  }
>                  w2=w1;w1=pre[w1];
>               }   
>               return f[u]*c[u];
>            } 
>            for(int w=1;w<len;w++){
>                 if(visit[w]==0){
>                     if(num[u][w].rf>0 && c[w]>c[u]-num[w][u].c){
>                          c[w]=c[u]-num[w][u].c;
>                          f[w]=f[u]<=num[u][w].rf?f[u]:num[u][w].rf;   
>                          pre[w]=u;
>                     }
>                     else if(c[w]>c[u]+num[u][w].cost){
>                          c[w]=c[u]+num[u][w].cost;
>                          f[w]=f[u]<=num[u][w].f?f[u]:num[u][w].f;
>                          pre[w]=u;    
>                     }                   
>                }      
>            }
>       }
> }
> void startfei(int t){
>      int v=0; 
>      while(true){
>         for(int i=1;i<=n;i++)
>            for(int j=n+1;j<=n+m;j++)
>                num[i][j].f=mins(supply[i][t],stock[j][t]);
>          for(int i=0;i<len;i++)
>              for(int j=0;j<len;j++)
>                   if(num[i][j].f==0) num[i][j].cost=maxs;
>                   else num[i][j].cost=num[i][j].c;
>         v=feiyong(t);
>         if(v==maxs) break;
>         sum+=v;     
>      }     
> }
> void input(){
>      int v; flat=false;
>      sum=0; len=n+m+2;
>      for(int i=1;i<=n;i++)
>           for(int j=0;j<k;j++)
>               scanf("%d",&supply[i][j]);
>      for(int i=n+1;i<=n+m;i++)
>           for(int j=0;j<k;j++)
>               scanf("%d",&stock[i][j]); 
>      for(int t=0;t<k;t++){
>         memset(num,0,sizeof(num));
>         for(int i=1;i<=n;i++)
>             for(int j=n+1;j<=n+m;j++)
>                scanf("%d",&num[i][j].c);    
>         for(int i=1;i<=n;i++) num[0][i].f=maxs; 
>         for(int i=n+1;i<=n+m;i++) num[i][n+m+1].f=maxs; 
>         if(!flat){  
>               startfei(t);
>               for(int i=1;i<=n;i++) if(supply[i][t]!=0){flat=true; break;}
>         }
>      }          
> }
> int main()
> {
>      while(true){
>          scanf("%d%d%d",&n,&m,&k);
>          if(n==0 && m==0 && k==0) break;
>          input();    
>          if(flat) printf("-1\n");
>          else printf("%d\n",sum);          
>      }
>      system("pause");
>      return 0;
> }

• Re:我WA了why？我是用dijstra方法写出的费用流2195能过这道题却？？？哪位大牛看一下撒 (124) drn 2012-10-08 21:44:17
  • Re:我WA了why？我是用dijstra方法写出的费用流2195能过这道题却？？？哪位大牛看一下撒 (20) sheeper 2012-12-14 18:11:44