P1285 队员分组
模拟赛出了一道只用求较小的一个组的人数的这题。
赛时编了一个时间复杂度卡满可能会被卡常的做法，大概是这样的：
如果给定的图是完全图，那么答案就是 \(\lfloor\frac{n}{2}\rfloor\)，否则就一定存在点对 \((u,v)\) 满足 \(u\)，\(v\) 之间没有边相连。将 \(u\) 塞进点集 \(S\)，\(v\) 塞进点集 \(T\) 表示这两个点肯定被放到两个不同的点集。然后枚举每一个点 \(w\)，如果 \(w\) 与 \(S\) 中的一个点之间没有边相连但与 \(T\) 中的每个点都有边相连那么 \(w\) 就加入 \(T\) 点集；反之加入 \(S\) 点集。如果两个集合都存在一个点不与 \(w\) 相连，那么就无解，如果目前两个点集中的点都与 \(w\) 有边相连就等下一轮枚举时再判断（因为上述判断会与加入顺序有关）。这里需要注意，可能会出现一个点一直到最后都与两个集合中的每一个点之间有边，这会导致这个点一直无法加入任何一个点集。但是可以注意到这样的只可能是一个与所有点之间都有边的点。统计这样的点的个数，就可以让这些点不参与上述的操作了。
可以注意到上述的操作之后仍存在一些点目前没加入任何点集但是可以通过再加入一些点之后导出矛盾（与一个点集中的一个点之间没边）。可以发现这些点加入哪个点集与前面已确定加入哪个点集的点所在的点集已经无关了，所以将 \(S\)，\(T\) 清空重跑一边上面的操作即可。
然后每跑一轮上面的操作之后都会得到 \(S\)，\(T\) 两个点集的大小，跑一边背包即可。
不过上述的思路写的太急，我甚至不确定会不会有没考虑到的地方或者是假掉的地方。反正按照这种思路过了模拟赛的所有数据和 \(n\le15\) 的对拍。
那么我们来讲一讲正解：
首先建出原图的补图。如果补图中出现边 \(u\leftrightarrow v\)，那么就代表这两个点不能放在一个点集里。这是很明显的二分图，用二分图判定即可判断是否有解。然后对补图的连通块大小做 dp，即可求出答案。