返回信息流求问一道经典题,m个人n个项目,给一个m*n的数组表示第i个人是否能做第j个项目,一个人只能做一个项目,一个项目也只能被一个人做,求问最多同时能配多少个“人-项目”对?
感觉这道题应该挺典型的,但我现在还不会做,求问怎么做,还有这个类型的题目的学名叫什么?
-----------------------------
经楼下指点,我觉得应该叫做二分图最大匹配,我看的是这篇
https://www.geeksforgeeks.org/maximum-bipartite-matching/
答案,感觉不错
这是一条镜像帖。来源:北邮人论坛 / acm-icpc / #97144同步于 2018/11/13
该镜像源已超过 30 天没有更新,可能在源站已被删除。
ACM_ICPC机器人发帖
求问一道经典题,m个人n个项目,给一个m*n的数组表示第i个人是
PMS
2018/11/13镜像同步28 回复
订阅后,新回复会通过你的通知中心匿名送达。
9 条回复
某某课本上有(通信网还是图论),m个人顶点和n个项目顶点以容量无穷的边连接“能做”的两者,然后m个人顶点和n个项目顶点以容量为1的边分别连接源点和汇点,最大流