特殊的二分图匹配问题。
可以拆点后跑二分图最大匹配。复杂度$O(\sum r_i\sum c_i(\sum r_i+\sum c_i))$ ,可能会T 。
也可以直接跑最大流:源点S 向单位$i$连容量为$r_i$的边,单位$i$向餐桌$j$连容量为1的边,餐桌$j$向汇点T 连容量为$c_i$的边。这显然是个二分图。用Dinic求解最大流,复杂度为$O(nm\sqrt{\sum r_i+\sum c_i}) (注意本题中边数为$$nm$)
//我的Dinic板子肯定没有y总的好,你们可以看看y总的
const ll INF=1ll<<50;
#define MAXN 200011
struct edge
{
ll v,w,nxt;
}e[MAXN<<1|1];
ll cnt=1,last[MAXN],cur[MAXN];
void add_directed_edge(ll u,ll v,ll w)
{
e[++cnt].v=v,e[cnt].w=w;
e[cnt].nxt=last[u],last[u]=cnt;
}
void adde(ll u,ll v,ll w){add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
ll dep[MAXN];
bool bfs(ll s,ll t,ll n)
{
for(ll i=1;i<=n;++i)dep[i]=0,cur[i]=last[i];
std::queue<ll>q;
dep[s]=1,q.push(s);
while(q.size())
{
ll u=q.front();q.pop();
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(!dep[v]&&e[i].w>0)dep[v]=dep[u]+1,q.push(v);
}
}
return dep[t];
}
ll ex_flow(ll u,ll t,ll flow=INF)
{
if(u==t)return flow;
ll f=0;
for(ll &i=cur[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(dep[v]==dep[u]+1&&e[i].w>0)
{
ll tmp=ex_flow(v,t,min(e[i].w,flow-f));
e[i].w-=tmp,e[i^1].w+=tmp;
f+=tmp;
if(f==flow)return f;
}
}
return f;
}
ll Dinic(ll s,ll t,ll n)
{
ll ans=0;
while(bfs(s,t,n))ans+=ex_flow(s,t);
return ans;
}
ll a[MAXN],b[MAXN];
int main()
{
ll m=read(),n=read(),s=m+n+1,t=m+n+2,sumr=0;
for(ll i=1;i<=m;++i)a[i]=read(),sumr+=a[i],adde(s,i,a[i]);
for(ll i=m+1;i<=m+n;++i)b[i]=read(),adde(i,t,b[i]);
for(ll i=1;i<=m;++i)
for(ll j=m+1;j<=m+n;++j)adde(i,j,1);
if(Dinic(s,t,t)<sumr)return puts("0"),0;
puts("1");
for(ll u=1;u<=m;++u)
{
for(ll i=last[u];i;i=e[i].nxt)
if(e[i].v>m&&e[i].v<=m+n&&!e[i].w)printf("%lld ",e[i].v-m);
puts("");
}
return 0;
}
神wh!