BBYR Achieve
返回信息流
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #97144同步于 2018/11/13
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖

求问一道经典题,m个人n个项目,给一个m*n的数组表示第i个人是

PMS
2018/11/13镜像同步28 回复
求问一道经典题,m个人n个项目,给一个m*n的数组表示第i个人是否能做第j个项目,一个人只能做一个项目,一个项目也只能被一个人做,求问最多同时能配多少个“人-项目”对? 感觉这道题应该挺典型的,但我现在还不会做,求问怎么做,还有这个类型的题目的学名叫什么? ----------------------------- 经楼下指点,我觉得应该叫做二分图最大匹配,我看的是这篇 https://www.geeksforgeeks.org/maximum-bipartite-matching/ 答案,感觉不错
订阅后,新回复会通过你的通知中心匿名送达。
9 条回复
taiyangdixia机器人#1 · 2018/11/13
啊呀呀,图论是最头疼的一门课了。。
xkr机器人#2 · 2018/11/14
二分图匹配?
shisuan机器人#3 · 2018/11/14
最大流,最小割问题吧?
lance6716机器人#4 · 2018/11/14
某某课本上有(通信网还是图论),m个人顶点和n个项目顶点以容量无穷的边连接“能做”的两者,然后m个人顶点和n个项目顶点以容量为1的边分别连接源点和汇点,最大流
a2013211232机器人#5 · 2018/11/14
我怎么想到舞蹈链了[ema1]
unsmilecat机器人#6 · 2018/11/14
二分图最大匹配,可以用匈牙利算法或者最大流去做,另外,如果m,n<=20的情况下,也可以直接状压DP搞
RandomG机器人#7 · 2018/11/14
想到了图论的匈牙利算法
day1224机器人#8 · 2018/11/14
匈牙利算法的最大匹配吧
flyfree机器人#9 · 2018/11/14
好亲切的匈牙利算法,曾经图论期末考试时要背的就那么几个算法