p3429 sol（POI2005 DWA）

考虑到 $n\le200$，不妨直接暴力设每个人在哪个派对中。列出 $n$ 个异或方程表示每个人与他在同一个派对的邻居数必须为偶数。具体而言，设 $deg_i$ 表示节点 $i$ 的度数，$cl_i=0/1$ 表示节点 $i$ 所在的派对（这里用 $0/1$ 表示），那么

高斯消元解方程组即可。

那么如何解决题目要求的满足尽可能多的人呢？答案是不用满足。接下来证明答案一定为 $n$。

考虑到异或方程组若有解那么答案为 $n$，若无解，则必然可以将若干个方程异或起来，使得未知变量的系数均为 $0$，而常量为 $1$。

由于只有度数为奇数的点才能产生常量为 $1$ 的方程，所以上述异或起来的方程中一定有奇数个对应了度数为奇数的点。但是未知变量系数均为 $0$ 就说明每个点都被异或了偶数次。

考虑每个被选择的奇数点一定有奇数个邻居被选择，剩余节点一定有偶数个邻居被选择。根据此，对于原图的边 $(u,v)$，若两者均被选择，则在新图中连接 $(u,v)$。

根据如上分析，可以得到原图中被选中的奇数点在新图中度数为奇数，其余被选中的点度数为偶数。度数之和为奇数，与一张图度数和总为偶数矛盾。

故有解。