P3254 圆桌问题

思路：最大流

提交：(1)次

题解：

我们把一个人看成一单位流量。从源点向每一个单位连一条容量为单位人数的边，从每一个单位向每一条餐桌连一条容量为(1)的边，相当于限制一个餐桌同一个单位只能去一个人，然后从每一个餐桌向汇点连一条容量为餐桌人数的边。跑最大流。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0;
  register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
  do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=430,M=42000,Inf=1e+9;
int n,m,s,t,cnt=1,ans,sum; bool flg;
int vr[M<<1],nxt[M<<1],w[M<<1],fir[N],cur[N],d[N],c[N],h[N];
inline void add(int u,int v,int ww) {vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,fir[u]=cnt;}
inline bool bfs() { memset(d,0,sizeof(d));
  queue<int> q; q.push(s),d[s]=1,cur[s]=fir[s];
  while(!q.empty()) { R u=q.front(); q.pop();
    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
      if(!d[v]&&w[i]) d[v]=d[u]+1,cur[v]=fir[v],q.push(v);
    } 
  } return d[t]>0;
}
inline int dfs(int u,int f) {
  if(u==t||f<=0) return f; R sum=f;
  for(R& i=cur[u];i;i=nxt[i]) { R v=vr[i];
    if(d[v]==d[u]+1&&w[i]) {
      R tmp=dfs(v,min(sum,w[i]));
      if(!tmp) d[v]=0;
      sum-=tmp,w[i]-=tmp,w[i^1]+=tmp;
      if(!sum) return f;
    }
  } return f-sum;
}
inline void dinic() {while(bfs()) ans+=dfs(s,Inf);}
inline void main() {
  g(n),g(m),s=n+m+1,t=n+m+2; for(R i=1;i<=n;++i) g(c[i]),add(s,i,c[i]),add(i,s,0),sum+=c[i];
  for(R i=1;i<=n;++i) for(R j=1;j<=m;++j) add(i,n+j,1),add(n+j,i,0);
  for(R i=1;i<=m;++i) g(h[i]),add(n+i,t,h[i]),add(t,n+i,0);
  dinic(); if(ans<sum) return (void) printf("0
"); printf("1
");
  for(R u=1;u<=n;++u,putchar('
')) for(R i=fir[u];i;i=nxt[i]) if(!w[i]) printf("%d ",vr[i]-n);
}
} signed main() {Luitaryi::main(); return 0;}

2019.08.19
81