hdu 2426 Interesting Housing Problem (二分图最佳匹配,km算法)

hdu 2426 题目链接

题意:n个学生,m个宿舍,每个学生住一个宿舍,然后n个学生给若干个宿舍打分,分数可正可0可负,学生不能住打的分为负的宿舍,或者没有打分的宿舍。问在满足上述条件的前提下,所有学生住的宿舍的分数之和最大是多少。如果无解输出-1.

 

思路:二分图最佳匹配。。。读漏题QAQ. 原来分数为负的房间是不能住的啊。。。。

考虑无解的情况,如果学生数比宿舍数多,无解。

如果一个学生不喜欢任何宿舍或者没给任何宿舍打分,无解。

然后KM.

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz