工厂(factory)

本题显然是一个二分图模型，左边 \(n\) 个点表示工人，右边 \(n\) 个点表示机器，左右两个点有边当且仅当对应工人会操作该机器。本题所求的最终情况就等价于，任意一个极大匹配都是完美匹配。

考虑一个弱化版本：判断目前情况是否满足任意一个极大匹配都是完美匹配。
观察可以发现，任意一个极大匹配都是完美匹配当且仅当任意一个联通块都是左右点数相等的完全二分图。
充分性显然所以只证明必要性。

证明：（反证）
假设存在一张二分图，存在一个联通块不是左右点数相等的完全二分图，
同时满足任意一个极大匹配都是完美匹配。

首先这个联通块左右点数必然相等。
这个联通块不是完全二分图，设左边的 \(a\) 点和右边的 \(b\) 点之间没有边，那么让这个联通块的其他点都匹配起来就不合法了且为极大匹配，寄了。

那么最终我们需要做的就是将所有 \((x_i, y_i)\) 划分如若干个集合，对于每个集合 \(s\) \(\Sigma_{i\in s}x_i = \Sigma_{i \in s}y_i\) 并且要最小化 \((\Sigma_{i \in s}x_i) ^ 2\)。

状压\(dp\)。 \(dp_{s,i}\) 表示集合 \(s\) 中已经划分出的满足要求的集合的 \(\Sigma x=i\) 的最小代价。

对于相同的 \((x_i, y_i)\) 只用关心个数，当 \(n=30\) 时，本质不同的集合个数很小，可以通过本题。

原文地址：http://www.cnblogs.com/SouthernWay/p/16856565.html