LOJ 2979 「THUSCH 2017」换桌——多路增广费用流

原来的思路：

　　优化连边。一看就是同一个桌子相邻座位之间连边、相邻桌子对应座位之间连边。

　　每个座位向它所属的桌子连边。然后每个人建一个点，向若干桌子连边。

　　因为连边的桌子是区间，所以线段树优化。

　　又想到志愿者招募之类的，所以想弄一个上下界费用流。人向它的座位连下界为1的边，对应桌子区间向人连边。找一些循环流。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

const int N=,M=,N2=,M2=,INF=;

int n,m,S,T,L[N][M],R[N][M],dy[N],bh[N][M],tot,Ls[N<<],Rs[N<<];

int rd[N2],hd[N2],xnt=,to[M2],nxt[M2],cap[M2],w[M2];

int ans,dis[N2],pr[N2],info[N2]; bool ins[N2];

queue<int> q;

void add(int x,int y,int l,int r,int z)

{

  rd[y]+=l; rd[x]-=l; ans+=l*z; r-=l;

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=r;w[xnt]=z;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;w[xnt]=-z;

}

void build(int l,int r,int cr)

{

  if(l==r){dy[l]=cr;return;}

  int mid=l+r>>;

  ls=++tot; build(l,mid,ls);

  rs=++tot; build(mid+,r,rs);

  add(ls,cr,,INF,); add(rs,cr,,INF,);

}

void qry(int l,int r,int cr,int L,int R,int k)

{

  if(l>=L&&r<=R)

    {

      printf("(%d->%d)\n",cr,k);

      add(cr,k,,,);return;

    }

  int mid=l+r>>;

  if(L<=mid)qry(l,mid,ls,L,R,k);

  if(mid<R)qry(mid+,r,rs,L,R,k);

}

bool spfa()

{

  memset(dis,0x3f,sizeof dis); info[T]=;

  dis[S]=; info[S]=INF; q.push(S); ins[S]=;

  while(q.size())

    {

      int k=q.front(); q.pop(); ins[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(cap[i]&&dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        pr[v]=i; info[v]=Mn(info[k],cap[i]);

        if(!ins[v])ins[v]=,q.push(v);

      }

    }

  return info[T];

}

int ek()

{

  int tp=info[T];

  for(int i=pr[T];i;i=pr[to[i^]])

    {

      cap[i]-=tp; cap[i^]+=tp;

      ans+=w[i]*tp;

      printf("%d ",to[i]);

    }

  puts("");

  return tp;

}

int main()

{

  n=rdn();m=rdn();

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

    for(int j=;j<=m;j++)L[i][j]=rdn()+;//+1

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

    for(int j=;j<=m;j++)R[i][j]=rdn()+;

  tot=;build(,n,); int tmp=n*m;

  for(int i=;i<=n;i++,puts(""))

    for(int j=;j<=m;j++)bh[i][j]=++tot,printf("%d ",tot);

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

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

      {

    qry(,n,,L[i][j],R[i][j],bh[i][j]+tmp);

    printf("(%d->%d)\n",bh[i][j]+tmp,bh[i][j]);

    add(bh[i][j]+tmp,bh[i][j],,,);

    printf("(%d->%d)\n",bh[i][j],dy[i]);

    add(bh[i][j],dy[i],,,);

    printf("(%d->%d)[]\n",bh[i][j],bh[i][j==m?:j+]);

    add(bh[i][j],bh[i][j==m?:j+],,INF,);

    printf("(%d->%d)[]\n",bh[i][j],bh[i][j>?j-:m]);

    add(bh[i][j],bh[i][j>?j-:m],,INF,);

    if(i<n)

      {

        printf("(%d->%d)[]\n",bh[i][j],bh[i+][j]);

        add(bh[i][j],bh[i+][j],,INF,);

      }

      }

  tot+=tmp; S=tot+; T=tot+; tmp=;

  printf("S=%d T=%d\n",S,T);

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

    if(rd[i]<)add(i,T,,-rd[i],);

    else if(rd[i]>)add(S,i,,rd[i],),tmp+=rd[i];

  printf("tmp=%d ans=%d\n",tmp,ans);

  while(spfa())tmp-=ek();

  if(tmp)puts("no solution");

  else printf("%d\n",ans);

  return ;

}

然后发现过不了样例。这样是不行的。希望的是 “因为自己连向 x 座位、 y 桌子向自己连边，所以 x 座位到 y 桌子走了一条路” ，但实际上这样相当于自己给 x 座位一些流量、自己向 y 桌子索求一些流量；如果有另一个人，给 y 桌子某座位一些流量、向 x 座位所在桌子索求流量，那么 x 和 y 之间本应有两条路，现在一条也没有了。

正解和这个类似？

每种座位都建两棵线段树，维护所有桌子，一棵表示向左走，一棵表示向右走；即一共 2*m 棵线段树。

然后每个人向线段树对应节点连边；线段树叶子就表示座位；同一个桌子的座位之间连边即可。

向左走的线段树，从自己到左孩子连的边，费用需要加上 “跨过右孩子” 的代价。即到达向左走的线段树某节点，默认当前在该区间的右端点。所以每个人向区间连的 log 条边要注意一下初始费用。

需要多路增广费用流才能过。多路增广，就是 spfa 一次之后，根据 dis[ cr ] 和 dis[ v ] 的关系，像 dinic 一样走。 dinic 的优化都可以加（似乎一定要加当前弧优化？），注意要像 dfs 一样打 vis 标记，因为 dis 上可能有 0 环。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define ls Ls[cr]

#define rs Rs[cr]

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

int Mx(int a,int b){return a>b?a:b;}

const int N=,M=,INF=;

int n,m,S,T,L[][],R[][],bh[][];

int tot,Ls[N],Rs[N],hd[N],xnt=,to[M],nxt[M],cap[M],w[M];

int ans,mxflow,dis[N],pr[N],info[N]; bool ins[N];

int cur[N];bool vis[N];

queue<int> q;

void add(int x,int y,int c,int z)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=c;w[xnt]=z;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;w[xnt]=-z;

}

void build(int l,int r,int cr,bool fx,int k)

{

  if(l==r)

    {

      if(!fx)bh[l][k]=++tot;

      add(cr,bh[l][k],INF,); return;

    }

  int mid=l+r>>;

  ls=++tot; build(l,mid,ls,fx,k);

  rs=++tot; build(mid+,r,rs,fx,k);

  if(fx)

    { add(cr,ls,INF,); add(cr,rs,INF,(mid-l+)*);}

  else

    { add(cr,ls,INF,(r-mid)*); add(cr,rs,INF,);}

}

void qry(int l,int r,int cr,int L,int R,int lj,bool fx)

{

  if(l>=L&&r<=R){ add(tot,cr,,lj);return;}

  int mid=l+r>>;

  if(!fx)

    {

      if(L<=mid)qry(l,mid,ls,L,R,lj+*(r-mid),fx);

      if(mid<R)qry(mid+,r,rs,L,R,lj,fx);

    }

  else

    {

      if(L<=mid)qry(l,mid,ls,L,R,lj,fx);

      if(mid<R)qry(mid+,r,rs,L,R,lj+*(mid-l+),fx);

    }

}

bool spfa()

{

  memset(dis,0x3f,sizeof dis); info[T]=;

  dis[S]=; info[S]=INF; q.push(S); ins[S]=;

  while(q.size())

    {

      int k=q.front(); q.pop(); ins[k]=;

      for(int i=hd[k],v;i;i=nxt[i])

    if(cap[i]&&dis[v=to[i]]>dis[k]+w[i])

      {

        dis[v]=dis[k]+w[i];

        pr[v]=i; info[v]=Mn(info[k],cap[i]);

        if(!ins[v])ins[v]=,q.push(v);

      }

    }

  return info[T];

}

int dfs(int cr,int flow)

{

  if(cr==T)return flow;

  int use=; vis[cr]=;

  for(int &i=cur[cr],v;i;i=nxt[i])

    if(cap[i]&&!vis[v=to[i]]&&dis[v]==dis[cr]+w[i])

      {

    int tmp=dfs(v,Mn(flow-use,cap[i]));

    if(!tmp)dis[v]=-;

    cap[i]-=tmp; cap[i^]+=tmp; ans+=tmp*w[i];

    use+=tmp; if(use==flow){vis[cr]=;return use;}

      }

  vis[cr]=; return use;

}

void solve()

{

  int tmp;

  while(spfa())

    {

      memcpy(cur,hd,sizeof hd);

      while(tmp=dfs(S,INF))mxflow+=tmp;

    }

}

int main()

{

  n=rdn();m=rdn();

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

    for(int j=;j<=m;j++) L[i][j]=rdn()+;//+1

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

    for(int j=;j<=m;j++) R[i][j]=rdn()+;

  tot=*m;

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

    { build(,n,i,,i); build(,n,i+m,,i);}

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

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

      { add(bh[i][j],bh[i][j==m?:j+],INF,);

    add(bh[i][j],bh[i][j==?m:j-],INF,);}

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

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

      {

    tot++;

    if(L[i][j]<i)

      qry(,n,j,L[i][j],Mn(i-,R[i][j]),-*(n-i),);

    if(R[i][j]>=i)

      qry(,n,j+m,Mx(L[i][j],i),R[i][j],-*(i-),);

      }

  S=tot+; T=tot+;

  for(int i=tot-n*m+;i<=tot;i++)add(S,i,,);

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

    for(int j=;j<=m;j++)add(bh[i][j],T,,);

  solve();

  if(mxflow<n*m)puts("no solution");

  else printf("%d\n",ans);

  return ;

}

巴特西

LOJ 2979 「THUSCH 2017」换桌——多路增广费用流

最新文章

热门文章