建图:从源点向单位连边,边权为单位人数,从单位向圆桌连边,边权为1,从圆桌向汇点连边,边权为圆桌容量。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack> using namespace std; template<const int _n>
struct Edge
{
struct Edge_base { int to,w,next; }e[_n];
int cnt,p[_n];
Edge() { clear(); }
void clear() { cnt=,memset(p,,sizeof(p)); }
int start(const int x) { return p[x]; }
Edge_base& operator[](const int x) { return e[x]; }
void insert(const int x,const int y,const int z)
{ e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }
}; int n,m,SSS,TTT;
int level[],cur[];
Edge<> e; bool Bfs(const int S)
{
int i,t;
queue<int> Q;
memset(level,,sizeof(int)*(n+m+));
level[S]=;
Q.push(S);
while(!Q.empty())
{
t=Q.front(),Q.pop();
for(i=e.start(t);i;i=e[i].next)
{
if(!level[e[i].to] && e[i].w)
{
level[e[i].to]=level[t]+;
Q.push(e[i].to);
}
}
}
return level[TTT];
} int Dfs(const int S,const int bk)
{
if(S==TTT)return bk;
int rest=bk;
for(int &i=cur[S];i;i=e[i].next)
{
if(level[e[i].to]==level[S]+ && e[i].w)
{
int flow=Dfs(e[i].to,min(rest,e[i].w));
e[i].w-=flow;
e[i^].w+=flow;
if((rest-=flow)<=)break;
}
}
if(rest==bk)level[S]=;
return bk-rest;
} int Dinic()
{
int flow=;
while(Bfs(SSS))
{
memcpy(cur,e.p,sizeof(int)*(n+m+));
flow+=Dfs(SSS,0x3f3f3f3f);
}
return flow;
} int main()
{
freopen("roundtable.in","r",stdin);
freopen("roundtable.out","w",stdout);
int i,j,w,c,Sum=; scanf("%d%d",&n,&m);
SSS=n+m+;TTT=SSS+;
for(i=;i<=n;++i)
{
scanf("%d",&w);
e.insert(SSS,i,w);
e.insert(i,SSS,);
for(j=;j<=m;++j)
{
e.insert(i,j+n,);
e.insert(j+n,i,);
}
Sum+=w;
}
for(i=;i<=m;++i)
{
scanf("%d",&c);
e.insert(i+n,TTT,c);
e.insert(TTT,i+n,);
} printf("%d\n",Dinic()==Sum?:); stack<int> St;
for(int t=;t<=n;++t)
{
for(i=e.start(t);i;i=e[i].next)
{
if(e[i].to==SSS)continue;
if(e[i].w==)St.push(e[i].to-n);
}
while(!St.empty())printf("%d ",St.top()),St.pop();
printf("\n");
} return ;
}
05-07 15:26