题解 P3429 [POI2005] DWA-Two Parties

耳朵龙_ · 2023-09-20 21:27:01 · 题解

本题现有题解没有提供答案为 n 的证明，补一个证明。

将人看做点，认识关系看作无向边，原题意等价于：给定一张无向图，0/1 染色后，称一个点是好的，当且仅当与之相邻且同色的点的个数为偶数。构造一种染色方案使好点的个数最多。

记点 i 的颜色为 col_i，度数为 deg_i，图的边集为 E。

假设好点个数可以为 n，那么当好点数为 n 时，根据与点 i 相邻且同色的点的个数为偶数，可知点的颜色满足一个 n 行的异或方程组，第 i 行为：

若该方程组有解，那么容易构造出使好点个数为 n 的染色方案，下面证明该方程组一定有解。

若该方程组无解，则必然能将某几行异或起来，使得等号左边各未知数系数均为 0，而等号右边常数为 1。即存在 S\subseteq\mathbb{N^*}，\bigoplus\limits_{i\in S} 第 i 个方程左边 =0，\bigoplus\limits_{i\in S} 第 i 个方程右边 =1。

称点 i 被选择，当且仅当 i\in S。称 v 属于 u 的邻域，当且仅当 (u,v)\in E。则方程组无解当且仅当存在 S 使得：

• 选择了奇数个奇度点（右边异或和为 1）
• 每个被选择的奇度点的邻域内都选了奇数个点，其他点的邻域内都选了偶数个点（左边各未知数系数均为 0）

可以根据 S 构造一张无向图 G'，其点集与原图相同，边集为 \{(u,v)\mid u\in S\lor v\in S\}\cap E。由于 G' 是一张无向图，其度数和为偶数。在 G' 中，容易发现被选择的奇度点度数为奇数，而其他点度数为偶数，由于被选择的奇度点有奇数个，G' 的度数和为奇数。前后矛盾，因此这样的选点方案不存在，方程组有解。

高斯消元解该方程组，输出方案即可，时间复杂度 O\left(\frac{n^3}{\omega}\right)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,b[N];
bitset<N>a[N];
int main(){
    scanf("%d",&n);
    for(int i=1,l,x;i<=n;++i){
        scanf("%d",&l),a[i][n+1]=a[i][i]=l&1;
        while(l--) scanf("%d",&x),a[i][x]=1;
    }
    for(int i=1,l;i<=n;++i){
        for(l=i;l<=n&&!a[l][i];++l) ;
        if(l<=n){
            if(l^i) swap(a[i],a[l]);
            for(l=1;l<=n;++l) if(l!=i&&a[l][i]) a[l]^=a[i];
        }
    }
    for(int i=n;i;--i) if(a[i][i]&a[i][n+1]) b[++m]=i;
    printf("%d\n",m);
    while(m) printf("%d ",b[m--]);
    return 0;
}