题解 P3429 【[POI2005]DWA-Two Parties】
oscar
2017-09-22 18:32:40
【POI补全计划#13 POI2005 DWA】
首先照例吐槽翻译
题目的意思是将一张无向图的点分成两个集合，去掉所有跨越集合的边，使得尽量多的点度数为偶数，输出分到其中一个集合中的所有点，有SPJ
题面里的“允许一小部分人没有参加派对”和“并且尽量使一个居民在派对上的朋友数更多”都是骗人的
还是要仔细读英文题面
以下是题解
-----------------------------分割线-----------------------------
首先随便手画几个图
```plain
(1)---(2)
| \ |
| \ |
| \ |
(3)---(4)
```
之类的
手玩发现所有（画出来的）图都存在一种分割方案使得所有点剩余度数都为偶数（大胆猜想，不需证明）
然后考虑怎么输出方案
记第i个点度数为deg[i]，与第i个点有边相连的点构成的集合为adj[i]，某些数的异或和为XOR{条件}{内容}
记x[i]为i所属集合（0或1），按如下方式列方程
若deg[i]为偶数，则(XOR{j属于adj[i]}{x[j]}) == 0，即与i相邻的节点有偶数个在集合1中（这个公式可以对i分情况讨论得到）
否则deg[i]为奇数，则(XOR{j属于adj[i]}{x[j]}) xor x[i] == 1，即i节点和与i相邻的节点有奇数个在集合1中
这样就构造出来了n个未知数和n个方程
高斯消元搞一下就可以把方程解出来，然后输出所有x[i]==1的i就解决了
注意方程有多解，需要自己思考细节
贴代码：
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int deg[233],mat[233][233],val[233];
int main()
{
int n,tmp;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",& /* 这里有个luogu的bug，如果去掉这段注释的话代码会变为一个符号(°) */ deg[i]);
for(int j=1;j<=deg[i];j++)
{
scanf("%d",&tmp);
mat[i][tmp]=1;
}
if(deg[i]&1)mat[i][i]=val[i]=1;
}
for(int i=1;i<=n;i++)
{
int sw=0;
for(int j=i;j<=n;j++)
{
if(mat[j][i]==1)
{
sw=j;
break;
}
}
if(sw)
{
for(int j=i;j<=n;j++)
{
swap(mat[i][j],mat[sw][j]);
}
swap(val[i],val[sw]);
}
for(int j=i+1;j<=n;j++)
{
if(mat[j][i]==0)continue;
for(int k=i;k<=n;k++)
{
mat[j][k]^=mat[i][k];
}
val[j]^=val[i];
}
}
mat[n][n]=1;
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
{
if(mat[i][j])
{
for(int k=j;k<=n;k++)
{
mat[i][k]^=mat[j][k];
}
val[i]^=val[j];
}
}
mat[i][i]=1;
}
int sum=0;
for(int i=1;i<=n;i++)if(val[i])sum++;
printf("%d\n",sum);
for(int i=1;i<=n;i++)if(val[i])printf("%d ",i);
return 0;
}
```