圆桌问题

摘要

复习Dinic~

假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。

会议餐厅共有n 张餐桌,每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。

为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,给出满足要求的代表就餐方案。输出方案

简单的网络流建模

建边 含义
从源点向第i个单位的点连边,表示第i个单位有 个人
第i个单位到第j个餐桌最多1个人
第j个餐桌最多有 个人
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+6,INF=0x3f3f3f3f;

struct qxx{int nex,t,v;};
qxx e[M];
int h[N],cnt=1;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}
void add_flow(int f,int t,int v){add_path(f,t,v),add_path(t,f,0);}

int s,t;
int d[N];
queue<int> q;
bool bfs(){
memset(d,0,sizeof(d));
d[s]=1,q.push(s);
while(q.size()){
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(!w||d[v])continue;
d[v]=d[u]+1,q.push(v);
}
}
return d[t];
}
int dinic(int u,int flow){
if(u==t)return flow;
int rest=flow;
for(int i=h[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(!w||d[v]!=d[u]+1)continue;
int k=dinic(v,min(rest,w));
if(k)e[i].v-=k,e[i^1].v+=k,rest-=k;
else d[v]=0;
}
return flow-rest;
}

int m,n,sum;
int r[N],c[N];
int main(){
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)scanf("%d",&r[i]),sum+=r[i];
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
s=0,t=m+n+1;
for(int i=1;i<=m;i++){
add_flow(s,i,r[i]);
for(int j=1;j<=n;j++)add_flow(i,m+j,1);
}
for(int i=1;i<=n;i++)add_flow(m+i,t,c[i]);
int maxflow=0;
while(bfs())for(int i;i=dinic(s,INF);)maxflow+=i;
if(maxflow<sum)return puts("0"),0;
else puts("1");
for(int u=1;u<=m;u++){
for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v;
if(w)continue;
printf("%d ",v-m);
}
puts("");
}
return 0;
}