【BZOJ 2879】[Noi2012]美食节 费用流

时间：2023-11-11 16:10:26

思路同修车，就是多了一个骚气的操作：动态加边，我们通过spfa流的过程可以知道，我们一次只会跑一流量，最后一层边跑过就不会再悔改，所以说我们只会用到一大片里面的很少的点，所以我们如果可以动态加边的话我们的边的数量就会从n*m*p级别减少到p*n级别，点数的话有些点虽然存在但是由于我们没连上所以就不会有任何用。
这道题告诉我网络流的图并不是静态的他也是可以动态的变化，这道题只是动态得加一些边，还会有什么呢？这道题的动态加边只是为了提高时间效率，还有其他的作用吗？

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int M=;

const int P=;

const int O=P*M;

const int E=P*M*N*;

const int Inf=0x3f3f3f3f;

struct V{

  int to,next,c,f;

}c[E];

int head[O],t=;

inline void add(int x,int y,int z,int _){

  c[++t].to=y,c[t].next=head[x],c[t].f=z,c[t].c=_,head[x]=t;

}

int dis[O],anc[O],p[N];

int q[O],front,back;

bool in[O];

int n,m,sum;

int S,T,ans;

bool link[M][P];

int val[N][M];

#define food(a) (a)

#define cook(a,b) (((a)-1)*sum+(b)+n)

inline bool spfa(){

  memset(dis,0x3f,sizeof(dis));

  dis[S]=,in[S]=true,q[back++]=S;

  if(back==O)back=;

  while(front!=back){

    int x=q[front++];in[x]=false;

    if(front==O)front=;

    for(int i=head[x];i;i=c[i].next)

      if(c[i].f&&dis[x]+c[i].c<dis[c[i].to]){

        dis[c[i].to]=dis[x]+c[i].c,anc[c[i].to]=i;

        if(!in[c[i].to]){

          q[back++]=c[i].to,in[c[i].to]=true;

          if(back==O)back=;

        }

      }

  }

  return dis[T]!=Inf;

}

inline int shoot(){

  int f=Inf;

  for(int i=anc[T];i;i=anc[c[i^].to])f=std::min(f,c[i].f);

  for(int i=anc[T];i;i=anc[c[i^].to])c[i].f-=f,c[i^].f+=f;

  int key=c[anc[T]^].to-n;

  int y=key%sum==?sum:key%sum;

  int x=(key-y)/sum+;

  if(y!=sum&&link[x][y+]==false){

    link[x][y+]=true;

    for(int i=;i<=n;++i){

      add(food(i),cook(x,y+),,(y+)*val[i][x]);

      add(cook(x,y+),food(i),,-(y+)*val[i][x]);

    }

    add(cook(x,y+),T,,);

    add(T,cook(x,y+),,);

  }

  return f*dis[T];

}

int main(){

  scanf("%d%d",&n,&m);

  for(int i=;i<=n;++i)

    scanf("%d",&p[i]),sum+=p[i];

  S=sum*m+n+,T=S+;

  for(int i=;i<=n;++i){

    add(S,food(i),p[i],);

    add(food(i),S,,);

  }

  for(int i=;i<=m;++i){

      add(cook(i,),T,,);

      add(T,cook(i,),,);

      link[i][]=true;

    }

  for(int i=,x;i<=n;++i)

    for(int j=;j<=m;++j){

      scanf("%d",&x);

      add(food(i),cook(j,),,x);

      add(cook(j,),food(i),,-x);

      val[i][j]=x;

    }

  while(spfa())ans+=shoot();

  printf("%d",ans);

  return ;

}

相关文章