建立二分图，每个单位为X集合中的顶点，每个餐桌为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi顶点连接一条容量为该单位人数的有向边。 2、从每个Yi顶点向T连接一条容量为该餐桌容量的有向边。 3、X集合中每个顶点向Y集合中每个顶点连接一条容量为1的有向边。
求网络最大流，如果最大流量等于所有单位人数之和，则存在解，否则无解。对于每个单位，从X集合对应点出发的所有满流边指向的Y集合的顶点就是该单位人员的安排情况（一个可行解）。
【建模分析】
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
【问题另解】
贪心，更好的方法其实是贪心。首先把所有单位和餐桌按人数从大到小排序，一种适当的贪心策略就是对于每个单位，所有人每次尽量去剩余容量较大的餐桌就坐。按照这种贪心策略，如果某时发现有人已经无法就坐，则无解。具体方法为用线段树维护餐桌的剩余容量，按人数从多到少安排每个单位的人员，每次安排就是把容量餐桌前k大的餐桌人数减1（k为该单位人数）。为保证线段树前k位时刻为前k大，要维护第k与第k+1,k+2,...人数与第k相等的位置，减少第k大时要减少尽量靠后的，这样才能保证单调。
#include <iostream> #include <vector> #include <queue> #include <cstdio> #include <cstring> using namespace std; const int maxn = 500; const int INF = ~0u >> 1; struct Edge{ int from,to,cap,flow; }; vector<Edge> edges; vector<int> G[maxn]; int s,t,d[maxn],cur[maxn]; int a[maxn],b[maxn]; bool vst[maxn]; void Init() { for(int i = 0;i < maxn;++i) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back((Edge){from,to,cap,0}); edges.push_back((Edge){to,from,0,0}); int sz = edges.size(); G[from].push_back(sz-2); G[to].push_back(sz-1); } void Build(int n,int m) { s = 0,t = n+m+1; for(int i = 1;i <= n;++i){ AddEdge(s,i,a[i]); for(int j = 1;j <= m;++j) AddEdge(i,j+n,1); } for(int i = 1;i <= m;++i) AddEdge(i+n,t,b[i]); } bool BFS() { memset(vst,false,sizeof(vst)); queue<int> Q; Q.push(s); d[s] = 0; vst[s] = true; while(!Q.empty()){ int u = Q.front();Q.pop(); for(int i = 0;i < (int)G[u].size();++i){ Edge& e = edges[G[u][i]]; if(!vst[e.to]&&e.cap>e.flow){ vst[e.to] = true; d[e.to] = d[u] + 1; Q.push(e.to); } } } return vst[t]; } int DFS(int u,int a) { if(u == t||a == 0) return a; int f,flow = 0; for(int& i = cur[u];i < (int)G[u].size();++i){ Edge& e = edges[G[u][i]]; if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){ e.flow += f; edges[G[u][i]^1].flow -= f; flow += f; a -= f; if(a==0)break; } } return flow; } int Maxflow() { int flow = 0; while(BFS()){ memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } return flow; } void Print(int n,int m) { for(int u = 1;u <= n;++u){ for(int i = 0;i < (int)G[u].size();++i){ Edge& e = edges[G[u][i]]; if(e.flow == 1&&e.to!=t) printf("%d ",e.to-n); } puts(""); } } int main() { int n,m; // while(~scanf("%d%d",&n,&m)) // { scanf("%d%d",&n,&m); Init(); int sum = 0; for(int i = 1;i <= n;++i){ scanf("%d",&a[i]); sum += a[i]; } for(int i = 1;i <= m;++i) scanf("%d",&b[i]); Build(n,m); int flow = Maxflow(); if(flow>=sum){ puts("1"); Print(n,m); } else puts("0"); // } return 0; }