Description
假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri,i=1,2,...,n 。会议餐厅共有m张餐桌，每张餐桌可容纳ci(i=1,2, ,m) 个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法， 给出满足要求的代表就餐方案。 编程任务： 对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
Input
由文件input.txt提供输入数据。文件第1行有2 个正整数m和n，m表示单位数，n表 示餐桌数，1<=m<=150, 1<=n<=270。文件第2 行有m个正整数，分别表示每个单位的代表 数。文件第3 行有n个正整数，分别表示每个餐桌的容量。
Output
程序运行结束时，将代表就餐方案输出到文件output.txt 中。如果问题有解，在文件第 1 行输出1，否则输出0。接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要 求的方案，只要输出1 个方案。
题目不是太难，我在这里就做粗略的解释了，我们有M个公司，N个餐桌，要让每个人都有位子坐，并且来自同一个公司的人不能坐在一起，就是代表着同一个公司的只能坐在不同的地方，所以限流到每个餐桌为1，同时每个餐桌固定能坐的人数，每个公司固定能坐的人数，然后建边即可。不难
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <string> 5 #include <cstring> 6 #include <algorithm> 7 #include <limits> 8 #include <vector> 9 #include <stack> 10 #include <queue> 11 #include <set> 12 #include <map> 13 #define lowbit(x) ( x&(-x) ) 14 #define pi 3.141592653589793 15 #define e 2.718281828459045 16 #define INF 0x3f3f3f3f 17 #define HalF (l + r)>>1 18 #define lsn rt<<1 19 #define rsn rt<<1|1 20 #define Lson lsn, l, mid 21 #define Rson rsn, mid+1, r 22 #define QL Lson, ql, qr 23 #define QR Rson, ql, qr 24 #define myself rt, l, r 25 using namespace std; 26 typedef unsigned long long ull; 27 typedef long long ll; 28 const int S = 0, maxN = 427, maxE = 9e4 + 7; 29 int M, N, T, head[maxN], cur[maxN], cnt, all; 30 struct Eddge 31 { 32 int nex, to, flow; 33 Eddge(int a=-1, int b=0, int c=0):nex(a), to(b), flow(c) {} 34 }edge[maxE]; 35 inline void addEddge(int u, int v, int flow) 36 { 37 edge[cnt] = Eddge(head[u], v, flow); 38 head[u] = cnt++; 39 } 40 inline void _add(int u, int v, int flow) { addEddge(u, v, flow); addEddge(v, u, 0); } 41 int deep[maxN]; 42 queue<int> Q; 43 bool bfs() 44 { 45 memset(deep, 0, sizeof(deep)); deep[S] = 1; 46 while(!Q.empty()) Q.pop(); 47 Q.push(S); 48 while(!Q.empty()) 49 { 50 int u = Q.front(); Q.pop(); 51 for(int i=head[u], v, f; ~i; i=edge[i].nex) 52 { 53 v = edge[i].to; f = edge[i].flow; 54 if(f && !deep[v]) 55 { 56 deep[v] = deep[u] + 1; 57 Q.push(v); 58 } 59 } 60 } 61 return deep[T]; 62 } 63 int dfs(int u, int dist) 64 { 65 if(u == T) return dist; 66 for(int &i=cur[u], v, f; ~i; i=edge[i].nex) 67 { 68 v = edge[i].to; f = edge[i].flow; 69 if(f && deep[v] == deep[u] + 1) 70 { 71 int di = dfs(v, min(dist, f)); 72 if(di) 73 { 74 edge[i].flow -= di; 75 edge[i^1].flow += di; 76 return di; 77 } 78 } 79 } 80 return 0; 81 } 82 int Dinic() 83 { 84 int ans = 0, tmp; 85 while(bfs()) 86 { 87 for(int i=S; i<=T; i++) cur[i] = head[i]; 88 while((tmp = dfs(S, INF))) ans += tmp; 89 } 90 return ans; 91 } 92 vector<int> vt[157]; 93 inline void solve() 94 { 95 for(int u=1; u<=M; u++) 96 { 97 for(int i=head[u], v, f; ~i; i=edge[i].nex) 98 { 99 v = edge[i].to; f = edge[i^1].flow; 100 if(v > M && f) vt[u].push_back(v - M); 101 } 102 } 103 for(int i=1, siz; i<=M; i++) 104 { 105 siz = (int)vt[i].size(); 106 for(int j=0; j<siz; j++) 107 { 108 printf("%d%c", vt[i][j], j == siz - 1 ? ' ' : ' '); 109 } 110 } 111 } 112 inline void init() 113 { 114 cnt = all = 0; T = N + M + 1; 115 memset(head, -1, sizeof(head)); 116 } 117 int main() 118 { 119 scanf("%d%d", &M, &N); 120 init(); 121 for(int i=1, num; i<=M; i++) 122 { 123 scanf("%d", &num); 124 _add(S, i, num); 125 all += num; 126 } 127 for(int i=1, num; i<=N; i++) 128 { 129 scanf("%d", &num); 130 _add(M + i, T, num); 131 } 132 for(int i=1; i<=M; i++) for(int j=M+1; j<=M+N; j++) _add(i, j, 1); 133 int ans = Dinic(); 134 if(ans < all) { printf("0 "); return 0; } 135 printf("1 "); 136 solve(); 137 return 0; 138 }