【做题记录】 ZJOI2009 假期的宿舍

  • \(\text{ZJOI2009}\) 假期的宿舍

    • 算法:二分图匹配、最大流

题目:

有一些人,在一个学校内上学。放假了,他们可能会在学校,也可能不在,这时他们的朋友会来看他们。每个人只能在他们认识的人的床上睡觉,问是否存在一个方案,使得不回家的学生和来看他们的朋友都有床睡。

\(T\) 组数据。

\(1\le n\le 50,1\le T\le 20\)

题解:

本来是打算搜最大流练手的。结果不知道为什么又水了一个匈牙利))

若干对人际关系、全都有床睡……

明显的二分图匹配。

考虑建图。

对于每一对认识的关系,连边。

如果既在学校又是学校学生,那么睡自己的床。

然后就是裸的二分图匹配。直接上匈牙利。

上一篇:SEAndroid安全机制对Android属性访问的保护分析


下一篇:二项式反演 学习笔记