额。。。其实挺简单的。。。只是我比较辣鸡，交了好几次才对。
这是一个二分图，从s到每一个单位连容量为人数的边，每个单位到每张餐桌连容量为1的边，餐桌到t连容量为餐桌可容纳人数的边，跑最大流即可。
然而辣鸡的我出现了各种错误。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int MAXN = 450; const int MAXM = 100000; const int INF = 0x3f3f3f3f; namespace Dinic { struct Edge { int u,v,c,f; Edge() {} Edge(int u, int v, int c, int f): u(u), v(v), c(c), f(f) {} }; int n,m,s,t; Edge edge[MAXM]; int head[MAXN],nxt[MAXM]; int dis[MAXN],cur[MAXN]; void init(int _n) { n = _n, m = 0; for(int i = 0; i < n; ++i) head[i] = -1; } void adde(int u, int v, int c) { edge[m] = Edge(u,v,c,0); nxt[m] = head[u]; head[u] = m++; edge[m] = Edge(v,u,0,0); nxt[m] = head[v]; head[v] = m++; } queue<int> q; bool bfs() { for(int i = 0; i < n; ++i) dis[i] = INF; dis[s] = 0; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dis[e.v] == INF) { dis[e.v] = dis[u] + 1; q.push(e.v); } } } return dis[t] != INF; } int dfs(int u, int res) { if(u == t || !res) return res; int flow = 0, f; for(int &i = cur[u]; ~i; i = nxt[i]) { Edge &e = edge[i]; if(e.c > e.f && dis[e.v] == dis[u] + 1) { f = dfs(e.v,min(res,e.c - e.f)); e.f += f; edge[i^1].f -= f; flow += f; res -= f; } } return flow; } int maxflow(int _s, int _t) { s = _s, t = _t; int flow = 0; while(bfs()) { for(int i = 0; i < n; ++i) cur[i] = head[i]; flow += dfs(s,INF); } return flow; } } int r[160],c[280]; int main() { int n,m; scanf("%d%d",&m,&n); int s = 0, t = m + n + 1; Dinic::init(t+1); for(int i = 1; i <= m; ++i) for(int j = 1; j <= n; ++j) Dinic::adde(i,m+j,1); for(int i = 1; i <= m; ++i) scanf("%d",r+i), Dinic::adde(s,i,r[i]); for(int i = 1; i <= n; ++i) scanf("%d",c+i), Dinic::adde(m+i,t,c[i]); int sum = 0; for(int i = 1; i <= m; ++i) sum += r[i]; if(sum > Dinic::maxflow(s,t)) { puts("0"); return 0; } puts("1"); for(int i = 1; i <= m; ++i) { for(int j = 1; j <= n; ++j) if(Dinic::edge[2*(n*(i-1)+j)-2].f) printf("%d ",j); puts(""); } return 0; } |