传送门 ↬
题目描述
有来自 m 个不同单位的代表参加一次国际会议。第 i 个单位派出了 ri 个代表。
会议的餐厅共有 n 张餐桌,第 i 张餐桌可容纳 ci 个代表就餐。
为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。
输入格式
输入的第一行是用空格隔开的两个整数,分别代表单位的个数 m 和餐桌的个数 n。
第二行有 m 个用空格隔开的整数,第 i 个整数代表第 i 个单位的代表人数 ri。
第三行有 n 个用空格隔开的整数,第 i 个整数代表第 i 张餐桌能容纳的人数 ci。
输出格式
本题存在 Special Judge。
请输出是否存在满足要求的就餐方案,若存在,请给出任意一种可行的方案。
输出的第一行是一个非 0 即 1 的整数,若存在方案则输出 1,否则输出 0。
若存在方案,则对于第 2 到第 (m+1) 行,在第 (i+1) 行输出 ri 个整数,代表第 i 个单位的代表就餐的餐桌编号。
输入输出样例
输入 #1
4 5
4 5 3 5
3 5 2 6 4
输出 #1
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
说明/提示
数据规模与约定
对于 $100\%$ 的数据,保证 1⩽m⩽150,1⩽n⩽270,1⩽ri,ci⩽103。
提示
请注意输入的第一行先读入 m 再读入 n。
分析
每个单位和每张餐桌各自都相互独立,只有单位的代表和餐桌会产生联系;要将 m 个单位的代表分配到 n 张餐桌上,显然可以转化为二分图多重匹配问题。
二分图左部为表示单位的节点,编号为 1∼m;右部为表示餐桌的节点,编号为 m+1∼m+n。进一步,我们要将二分图多重匹配问题转化为网络最大流问题。设立超级源点 s,超级汇点 t。s 向 1∼m 的节点连边,容量为各自单位的代表人数 ri,现实意义是每个单位至多有 ri 个人能分到餐桌;m+1∼m+n 的节点向 t 连边,容量为各个餐桌的容纳人数 ci,现实意义是每个餐桌至多容纳 ci 人就餐;1∼m 各个点都向 m+1∼m+n 的节点连边,容量为 1,每个单位节点都会向 n 个餐桌节点连边,总共建立 mn 条边,通过限制容量为 1,就限制了每张餐桌不可有相同单位的人同时就餐的条件。由于通过节点之间建边,已经满足题目匹配条件:每个单位有 ri 个代表,每张餐桌至多容纳 ci 人,同一个单位的不同代表不能分配到同一张餐桌。因此,网络最大流至多等于代表的总人数。
运行一次 Dinic 算法,即可求得网络最大流 maxflow。若最大流小于代表总人数,则不存在合法的匹配方案。若 maxflow 等于代表总人数,考虑输出匹配方案。由于单位节点和餐桌节点之间的连边容量至多为 1,因此边上只会存在零流和满流两种状态;若 i 指向 j 的边剩余容量为 0(i,j∈N∗,且 1⩽i⩽m,1⩽j−m⩽n),说明该边满流,第 i 个单位有一人被分配到 j−m 号餐桌。因此,我们不妨枚举左部点的出边,若该边剩余容量为 0,则输出该边的入点。
代码
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 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
|
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=503; const int inf=0x3f3f3f3f; struct E { int to; int cap; int Next=-1; }edge[N*N<<1]; int head[N],tot; int s,t; int depth[N]; int m,n; int in; void init(); inline void add_edge(int,int,int); bool bfs(); int dfs(int,int); int Dinic(); int main() { int i,j; cin>>m>>n; init(); for(i=1;i<=m;i++) { int r; scanf("%d",&r); add_edge(s,i,r); in+=r; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { add_edge(i,j+m,1); } } for(i=1;i<=n;i++) { int c; scanf("%d",&c); add_edge(i+m,t,c); } if(Dinic()==in) { puts("1"); for(i=1;i<=m;i++) { for(j=head[i];~j;j=edge[j].Next) { if(!edge[j].cap) { printf("%d ",edge[j].to-m); } } putchar('\n'); } } else puts("0"); return 0; } void init() { tot=1; memset(head,-1,sizeof(head)); s=0; t=n+m+1; } inline void add_edge(int u,int v,int cap) { tot++; edge[tot].to=v; edge[tot].cap=cap; edge[tot].Next=head[u]; head[u]=tot; tot++; edge[tot].to=u; edge[tot].cap=0; edge[tot].Next=head[v]; head[v]=tot; } bool bfs() { memset(depth,0,sizeof(depth)); queue<int>q; q.push(s); depth[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(register int i=head[x];~i;i=edge[i].Next) { int y=edge[i].to; if(edge[i].cap&&!depth[y]) { q.push(y); depth[y]=depth[x]+1; if(y==t) return 1; } } } return 0; } int dfs(int x,int flow) { if(x==t) return flow; int rest=flow; int temp; for(register int i=head[x];~i&&rest;i=edge[i].Next) { int y=edge[i].to; if(edge[i].cap&&depth[y]==depth[x]+1) { temp=dfs(y,min(rest,edge[i].cap)); if(!temp) depth[y]=0; edge[i].cap-=temp; edge[i^1].cap+=temp; rest-=temp; } } return flow-rest; } int Dinic() { int maxflow=0; while(bfs()) maxflow+=dfs(s,inf); return maxflow; }
|
后记
边的数量 tot 必须初始化为 1。