【BZOJ 1930】 [Shoi2003]pacman 吃豆豆最大费用最大流

如果你知道他是网络流的话你就很快会想到一个最大费用最大流的模型，然后你发现可能T，然而你发现你只用增广两次，然后你就开心的打了出来，然后发现被稠密图里spfa的丧病时间复杂度坑了，还是会T。于是我就开始找优化方式，一开始我想优化边数，可是发现，不会，然后我就开始瞎搞。我把第一遍spfa改成了最长上升子序列，第二遍是在第一遍的基础上建的图，由于没有反向边所以快了许多，然后就过了，高兴。我去看了看题解里面说的是优化边数，它的思路就是把一个边拆开，就是说，我们原来连边都是从前往后从低向高连（如果按照x排序的话），那么我们把两个点之间的边拆成最小，就是说，连边的两点之间不会有高度在其之间的点，虽然说这样连边仍然有可能把边数卡到百万级别但是会好很多，就是要注意这样做的话必须要让拆开的点之间连Inf流量以支持交通运输，所以我就把这两个东西结合了一下。
这道题的启发在于对于一些并不像网络流的东西进行网络流，以及通过观察特点来更加准确的估算时间复杂度以不至于做出错误判断，还有就是替换算法来提高时间效率，最重要的一点当然就是优化边数的方法，就是把各个边等效化同时增加一些边的功能以减少边数，换言之就是把边拆分，更准确的说就是找到基底。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int Inf=0x3f3f3f3f;

const int oo=0xafafafaf;

struct V{

  int to,next,c;

}c[N*N/];

int head[N*],t;

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

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

}

int dis[N*];

int cnt[N],anc[N];

int q[N*],front,back;

bool in[N*];

bool via[*N][*N];

int n;

int S,T,tail;

struct Point{

  int x,y;

}poi[N];

inline bool comp(Point a,Point b){

  return a.x<b.x||(a.x==b.x&&a.y<b.y);

}

inline void spfa(){

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

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

  if(back==(N<<))back=;

  while(front!=back){

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

    if(front==(N<<))front=;

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

      if(dis[x]+c[i].c>dis[c[i].to]){

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

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

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

          if(back==(N<<))back=;

        }

      }

  }

}

int main(){

  scanf("%d",&n);

  if(n==){

    printf("");

    return ;

  }

  if(n==){

    printf("");

    return ;

  }

  int ans=;

  S=n+n+,T=n+n+;

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

    scanf("%d%d",&poi[i].x,&poi[i].y);

  std::sort(poi+,poi+n+,comp);

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

    cnt[i]=,anc[i]=;

    for(int j=i-;j>;--j)

      if(poi[j].y<=poi[i].y&&cnt[i]<cnt[j]+)

        cnt[i]=cnt[j]+,anc[i]=j;

    if(cnt[i]>ans)

      ans=cnt[i],tail=i;

  }

  int last=T;

  for(int i=tail;i;i=anc[i]){

    via[i][i+n]=true;

    via[i+n][last]=true;

    add(last,i+n,);

    add(i+n,i,-);

    last=i;

  }

  via[S][last]=true;

  add(last,S,);

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

    add(S,i,);

    add(i+n,T,);

    if(via[i][i+n]==false)add(i,i+n,);

    add(i,i+n,);

    for(int j=i+,min=Inf;j<=n;++j)

      if(poi[j].y>=poi[i].y&&poi[j].y<min)

        add(i+n,j,),min=poi[j].y;

  }

  spfa(),ans+=dis[T];

  printf("%d",ans);

  return ;

}

结合的优秀代码

#include <cstdio>

#include <cstring>

#include <algorithm>

const int N=;

const int Inf=0x3f3f3f3f;

const int oo=0xafafafaf;

struct V{

  int to,next,f,c;

}c[N*N];

int head[N*],t=;

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

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

}

int dis[N*],anc[N*];

int q[N*],front,back;

bool in[N*];

int n;

int S,T,source;

struct Point{

  int x,y;

}poi[N];

inline bool look(Point a,Point b){

  return b.x>=a.x&&b.y>=a.y;

}

inline bool comp(Point a,Point b){

  return a.x<b.x||(a.x==b.x&&a.y<b.y);

}

inline bool spfa(){

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

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

  if(back==(N<<))back=;

  while(front!=back){

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

    if(front==(N<<))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==(N<<))back=;

        }

      }

  }

  return dis[T]!=oo;

}

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;

  return f*dis[T];

}

int main(){

  scanf("%d",&n);

  source=n+n+,S=n+n+,T=n+n+;

  add(S,source,,),add(source,S,,);

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

    scanf("%d%d",&poi[i].x,&poi[i].y);

  std::sort(poi+,poi+n+,comp);

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

    add(source,i,Inf,),add(i,source,,);

    add(i+n,T,Inf,),add(T,i+n,,);

    add(i,i+n,,),add(i+n,i,,-);

    add(i,i+n,Inf,),add(i+n,i,,);

    for(int j=i+,min=Inf;j<=n;++j)

      if(poi[j].y>=poi[i].y&&poi[j].y<min)

        add(i+n,j,Inf,),add(j,i+n,,),min=poi[j].y;

  }

  int ans=;

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

  printf("%d",ans);

  return ;

}

质朴的边优化费用流

巴特西

【BZOJ 1930】 [Shoi2003]pacman 吃豆豆最大费用最大流

最新文章

热门文章

巴特西

【BZOJ 1930】 [Shoi2003]pacman 吃豆豆 最大费用最大流

最新文章

热门文章

【BZOJ 1930】 [Shoi2003]pacman 吃豆豆最大费用最大流