题目链接：P3254 圆桌问题

题意

有来自 mmm 个不同单位的代表参加一次国际会议。第 iii 个单位派出了 ririri 个代表。会议的餐厅共有 nnn 张餐桌，第 iii 张餐桌可容纳 cicici个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

解析

匹配问题之三，多对多的匹配问题，解决问题方法还是建图。
000号:源点
111~mmm:代表单位
m+1m + 1m+1 ~ m+nm + nm+n:代表桌子
mmm + n+1n + 1n+1号: 汇点

1.1.1.源点流向单位的流量为该单位的代表人数ririri
2.2.2.每个单位最多可以向一张桌子派一个人，流量为111
3.3.3.每张桌子最多可以坐cicici个人，所以每张桌子流向汇点流量为cicici

看最终流量是否等于所有参会的人数即可，输出公司与餐桌连边流量为000的边（匹配上的）即可

代码

/**/
#include 
#include 
#include 
using namespace std;
const int N = 1000, M = 100000;int n,m,s,t,head[N],tot = 1;//注意要从1开始 即第一条边存储在e[2]中
struct edge
{int to,nex,w;
}e[M];
void add(int to,int from,int w)
{e[++ tot].w = w;e[tot].to = to;e[tot].nex = head[from];head[from] = tot;
}int dep[N];//用bfs分层
bool bfs()//判断是否还存在增广路
{queueq;q.push(s);for(int i = 0; i <= n + m + 1; i ++) dep[i] = 0;dep[s] = 1;while(!q.empty()){int u = q.front(); q.pop();for(int i = head[u]; i; i = e[i].nex){int v = e[i].to;if(e[i].w && !dep[v]){dep[v] = dep[u] + 1;if(v == t) return true;q.push(v);}}}return dep[t];
}int dfs(int u,int inflow)//in为进入的流,源点的流无限大
{if(u == t)//到达汇点return inflow;//返回这一条增广路的流量int outflow = 0;for(int i = head[u]; i && inflow; i = e[i].nex)//还有残余流量{int v = e[i].to;if(e[i].w && dep[v] == dep[u] + 1)//只搜索下一层次的点，防止绕回或走反向边{int flow = dfs(v , min(e[i].w, inflow));//min选取边残余容量与入流残余的最小值e[i].w -= flow; //减去达到汇点的增广流量e[i ^ 1].w += flow; //反向边增加流量inflow -= flow; //入流减少相同的outflow += flow; //增广路增加流量}}if(outflow == 0) dep[u] = 0;//通过u点不能到达汇点，剪枝return outflow;
}
int main()
{scanf("%d%d",&m,&n);/*0号:源点1~m:代表单位m + 1 ~ m + n:代表桌子m + n + 1: 汇点*/int sum = 0;for(int i = 1; i <= m; i ++){int cnt;scanf("%d",&cnt);sum += cnt;add(i, 0, cnt); // 源点流向单位的流量为该单位的代表人数riadd(0, i, 0);for(int j = 1; j <= n; j ++){add(j + m, i, 1); // 每个单位最多可以向一张桌子派一个人add(i, j + m, 0);}}for(int i = 1; i <= n; i ++){int cnt;scanf("%d",&cnt);add(m + n + 1, m + i, cnt); //每张桌子最多可以坐ci个人，所以每张桌子流向汇点流量为ciadd(m + i, m + n + 1, 0);}s = 0;t = m + n + 1;int ans = 0;while(bfs()){ans += dfs(s, 200000);}if(ans < sum){printf("0\n");return 0;}printf("1\n");for(int i = 1; i <= m; i ++){for(int j = head[i]; j; j = e[j].nex){if(e[j].to < n + m + 1 && !e[j].w) printf("%d ",e[j].to - m);}puts("");}return 0;
}