_{<center id="eb1ez"></center>}

[BZOJ2466][中山市選2009]樹(shù)（高斯消元+dfs）

2019-11-06 08:04:59

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

題目描述

傳送門(mén)

題解

開(kāi)關(guān)燈問(wèn)題。。。

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<bitset>#include<cmath>using namespace std;#define N 105int n,x,y,now,Min;int tot,point[N],nxt[N*2],v[N*2];bitset <N> a[N];int b[N],ans[N];void clear(){ x=y=now=Min=0; tot=0;memset(point,0,sizeof(point)); for (int i=1;i<=n;++i) a[i].reset(); memset(b,0,sizeof(b));memset(ans,0,sizeof(ans));}void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void dfs(int dep){ if (!dep) { Min=min(Min,now); return; } if (now>=Min) return; for (int i=dep+1;i<=n;++i) if (a[dep][i]) b[dep]^=ans[i]; if (a[dep][dep]) { ans[dep]=b[dep]; if (ans[dep]) ++now; dfs(dep-1); if (ans[dep]) --now; } else { ans[dep]=0; dfs(dep-1); ans[dep]=1;++now; dfs(dep-1); ans[dep]=0;--now; } for (int i=dep+1;i<=n;++i) if (a[dep][i]) b[dep]^=ans[i];}void gauss(){ for (int i=1;i<=n;++i) { if (!a[i][i]) { for (int j=i+1;j<=n;++j) if (a[j][i]) {a[i]^=a[j];b[i]^=b[j];break;} } for (int j=i+1;j<=n;++j) if (a[j][i]) a[j]^=a[i],b[j]^=b[i]; } dfs(n);}int main(){ while (~scanf("%d",&n)) { if (!n) break; clear(); for (int i=1;i<n;++i) { scanf("%d%d",&x,&y); add(x,y),add(y,x); } for (int i=1;i<=n;++i) { a[i][i]=1;b[i]=1; for (int j=point[i];j;j=nxt[j]) a[i][v[j]]=1; } Min=2100000000;gauss();