这道题建图还是很明白的：一个二分图，左边是单位，右边是餐桌，然后源点都向单位连一条容量为单位人数的边，每一个餐桌和汇点都连一条容量为餐桌容量的边（都叫容量~）。然后每一个单位向每一个餐桌都连一条容量为1的边，跑最大流即可。本来以为复杂度会很高，然而数据范围小，加上dinic玄学，很快就跑过了。
最后输出答案：如果最大流等于所有单位人数的话就说明满足要求，然后查询每一个单位的边的流量情况：如果这条边流满了，就说明该单位有一个人到了这一桌，那么输出该桌的编号。
后来知道这叫二分图多重匹配。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 455; 20 inline ll read() 21 { 22 ll ans = 0; 23 char ch = getchar(), last = ' '; 24 while(!isdigit(ch)) {last = ch; ch = getchar();} 25 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 26 if(last == '-') ans = -ans; 27 return ans; 28 } 29 inline void write(ll x) 30 { 31 if(x < 0) x = -x, putchar('-'); 32 if(x >= 10) write(x / 10); 33 putchar(x % 10 + '0'); 34 } 35 36 int m, n, t, Sum; 37 struct Edge 38 { 39 int from, to, cap, flow; 40 }; 41 vector edges; 42 vector G[maxn]; 43 void addEdge(int from, int to, int w) 44 { 45 edges.push_back((Edge){ from, to, w, 0}); 46 edges.push_back((Edge){to, from, 0, 0}); 47 int sz = edges.size(); 48 G[from].push_back(sz - 2); 49 G[to].push_back(sz - 1); 50 } 51 52 int dis[maxn]; 53 bool bfs() 54 { 55 Mem(dis); dis[0] = 1; 56 queue q; q.push(0); 57 while(!q.empty()) 58 { 59 int now = q.front(); q.pop(); 60 for(int i = 0; i < (int)G[now].size(); ++i) 61 { 62 Edge& e = edges[G[now][i]]; 63 if(!dis[e.to] && e.cap > e.flow) 64 { 65 dis[e.to] = dis[now] + 1; 66 q.push(e.to); 67 } 68 } 69 } 70 return dis[t]; 71 } 72 int cur[maxn]; 73 int dfs(int now, int res) 74 { 75 if(now == t || res == 0) return res; 76 int flow = 0, f; 77 for(int& i = cur[now]; i < (int)G[now].size(); ++i) 78 { 79 Edge& e = edges[G[now][i]]; 80 if(dis[e.to] == dis[now] + 1 && (f = dfs(e.to, min(res, e.cap - e.flow))) > 0) 81 { 82 e.flow += f; 83 edges[G[now][i] ^ 1].flow -= f; 84 flow += f; 85 res -= f; 86 if(res == 0) break; 87 } 88 } 89 return flow; 90 } 91 92 int maxflow() 93 { 94 int flow = 0; 95 while(bfs()) 96 { 97 Mem(cur); 98 flow += dfs(0, INF); 99 }100 return flow;101 }102 103 int main()104 {105 m = read(); n = read();106 t = n + m + 1;107 for(int i = 1; i <= m; ++i)108 {109 int x = read(); Sum += x;110 addEdge(0, i, x);111 for(int j = 1; j <= n; ++j) addEdge(i, j + m, 1);112 }113 for(int i = 1; i <= n; ++i) addEdge(i + m, t, read());114 if(maxflow() == Sum) 115 {116 write(1); enter;117 for(int i = 1; i <= m; ++i)118 {119 for(int j = 0; j < (int)G[i].size(); ++j)120 {121 Edge e = edges[G[i][j]];122 if(e.to > m && e.cap - e.flow == 0)123 write(e.to - m), space;124 }125 enter;126 }127 }128 else write(0), enter;129 return 0;130 }