99工厂

Description 题解 首先先转换题目,就是n个工人和n台机器,转换为二分图模型,左右两点有边当且仅当该人会该机器 无论哪种情况所有机器都有人操作,而且所有人都有事干,也就是每一个极大匹配都是完美匹配 然后有结论为任意一个极大匹配都是完美匹配当且仅当二分图中每一个联通块都是左右点数相同的完全二分图 证明如下: 然后我们回到问题本身,那么记录一开始每个联通块左右点数为(xi,yi)...