【高斯消元解xor方程组】BZOJ2466-[中山市选2009]树

时间:2023-03-08 15:45:44
【高斯消元解xor方程组】BZOJ2466-[中山市选2009]树

【题目大意】

给出一棵树,初始状态均为0,每反转一个节点的状态,相邻的节点(父亲或儿子)也会反转,问要使状态均为1,至少操作几次?

【思路】

一场大暴雨即将来临,白昼恍如黑夜!happy!

和POJ1222差不多,首先容易知道:每个节点最多被反转一次,证明略。

高斯消元解Xor方程组可能存在*元,即处理完后map[i][i]=0;则通过dfs来枚举所有的情况,求出最小的。

【错误点】

gauss里面交换值得时候不要忘了n+1也要跟着交换。

dfs里面的t我一开始直接是按照往常一样修改map[i][n+1],然而这个是dfs,map[i][n+1]的初始值后面还要用到。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=+;
const int INF=0x7fffffff;
int n,map[MAXN][MAXN],que[MAXN];
int ans; void Gauss()
{
for (int i=;i<=n;i++)
{
int t=i;
for (;t<=n && !map[t][i];t++);
if (t<=n)
{
if (t!=i) for (int j=i;j<=n+;j++) swap(map[i][j],map[t][j]);
for (int j=i+;j<=n;j++)
if (map[j][i])
for (int k=i;k<=n+;k++) map[j][k]^=map[i][k];//不要忘记这里要到n+1
}
}
} void dfs(int step,int now)
{
if (now>=ans) return;
if (!step)
{
ans=min(ans,now);
return;
}
if (map[step][step])
{
int t=map[step][n+];
//map[step][n+1]后续回溯中还要使用,所以要暂存给t
for (int i=step+;i<=n;i++)
if (map[step][i]) t^=que[i];//这里不要把step和i搞混了
que[step]=t;
dfs(step-,now+t);
}
else
{
que[step]=;dfs(step-,now);
que[step]=;dfs(step-,now+);
}
} void init()
{
ans=INF;
memset(que,,sizeof(que));
memset(map,,sizeof(map));
for (int i=;i<n-;i++)
{
int u,v;
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=;
}
for (int i=;i<=n;i++) map[i][i]=,map[i][n+]=;
} int main()
{
while (~scanf("%d",&n))
{
if (n==) break;
init();
Gauss();
dfs(n,);
printf("%d\n",ans);
}
return ;
}