【题目地址】点击打开链接
二分图多重匹配问题,可以用最大流解决。
【建模方法】
建立二分图,每个单位为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大时要减少尽量靠后的,这样才能保证单调。
//
//Created by just_sort 2016/12/30
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define MP(x, y) make_pair(x,y)
const int maxn = 2000;
const int maxm = 100010;
const int maxs = 10;
const int INF = 0x3f3f3f3f;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
struct G
{
int v, cap, next;
G() {}
G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化,qw队列
void init()
{
memset(p, -1, sizeof(p));
T = 0;
}
void add(int u, int v, int cap)
{
E[T] = G(v, cap, p[u]);
p[u] = T++;
E[T] = G(u, 0, p[v]);
p[v] = T++;
}
bool bfs(int st, int en, int n)
{
int i, u, v, head, tail;
for(i = 0; i <= n; i++) d[i] = -1;
head = tail = 0;
d[st] = 0;
qw[tail] = st;
while(head <= tail)
{
u = qw[head++];
for(i = p[u]; i + 1; i = E[i].next)
{
v = E[i].v;
if(d[v] == -1 && E[i].cap > 0)
{
d[v] = d[u] + 1;
qw[++tail] = v;
}
}
}
return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
if(u == en || f == 0) return f;
int flow = 0, temp;
for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
{
G& e = E[temp_p[u]];
if(d[u] + 1 == d[e.v])
{
temp = dfs(e.v, en, min(f, e.cap));
if(temp > 0)
{
e.cap -= temp;
E[temp_p[u] ^ 1].cap += temp;
flow += temp;
f -= temp;
if(f == 0) break;
}
}
}
return flow;
}
int dinic(int st, int en, int n)
{
int i, ans = 0;
while(bfs(st, en, n))
{
for(i = 0; i <= n; i++) temp_p[i] = p[i];
ans += dfs(st, en, INF);
}
return ans;
}
int main()
{
init();
int m, n;
scanf("%d%d", &m, &n);
int sum = 0;
for(int i = 1; i <= m; i++){
int x;
scanf("%d", &x);
sum += x;
add(n + i, n + m + 1, x);
}
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
add(0, i, x);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
add(i, j + n, 1);
}
}
if(sum != dinic(0, n + m + 1, n + m + 1)){
printf("0\n");
return 0;
}
puts("1");
for(int i = n + 1; i <= n + m; i++){
for(int j = p[i]; ~j; j = E[j].next){
if(j & 1){
if(E[j].cap == 1) printf("%d ", E[j].v);
}
}
printf("\n");
}
return 0;
}