p3429 sol（POI2005 DWA）

AllenJYL · 2024-12-18 20:53:41 · 题解

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

• 若 deg_i 是偶数，那么 \oplus_{v,(i,v)\in E}\ cl_v=0；
• 否则，考虑到与 i 在同一个派对的邻居数为偶数，而 i 本身显然与自己在同一个派对，所以 \oplus_{v,(i,v)\in E}\ cl_v\oplus cl_i=1。

高斯消元解方程组即可。

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

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

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

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

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

故有解。