-
\(\text{ZJOI2009}\) 假期的宿舍
- 算法:二分图匹配、最大流
题目:
有一些人,在一个学校内上学。放假了,他们可能会在学校,也可能不在,这时他们的朋友会来看他们。每个人只能在他们认识的人的床上睡觉,问是否存在一个方案,使得不回家的学生和来看他们的朋友都有床睡。
\(T\) 组数据。
\(1\le n\le 50,1\le T\le 20\)
题解:
本来是打算搜最大流练手的。结果不知道为什么又水了一个匈牙利))
若干对人际关系、全都有床睡……
明显的二分图匹配。
考虑建图。
对于每一对认识的关系,连边。
如果既在学校又是学校学生,那么睡自己的床。
然后就是裸的二分图匹配。直接上匈牙利。