首页 > 代码库 > [网络流专练5][圆桌问题]

[网络流专练5][圆桌问题]

题目描述

“假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为

ri i=1,2,……n 。会议餐厅共有 m张餐桌,每张餐桌可容纳ci i=1,2, ……,m 个代表就餐。
为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法,
给出满足要求的代表就餐方案。”

Solution

少了套路,多了真诚

1.套路

当然是对题目中敏感的对象建点

考虑对单位和餐桌建点,而不是个人建点(很容易走偏的思路)

2.算法

那么,很容易想出连边(任意单位i,任意餐桌j).(1),每个单位往每个餐桌连容量为1的边,代表只能去一个人

每个单位有k个人的话,连边(S,餐桌i).(ki)代表每个单位去了k个人

每个餐桌有固定人数限制,则用餐桌向汇点连边,(餐桌i,T).(m)

跑最大流算法,若最大流正好和所有单位人数之和相等,则存在解,否则无解

3.细节

如果要输出方案的话

如果用dinic,把流量flow和容量cap存成一个变量f的话,f=0的边的有用点输出就是了

如果用isap,把流量flow和容量cap分开存储,输出那些cap==flow的边的有用点就行

[网络流专练5][圆桌问题]