[bzoj2443][Usaco2011 Open]奇数度数_树形dp_生成树_并查集

时间:2022-10-20 20:39:58

奇数度数 bzoj-2443 Usaco-2011 Open

题目大意:给定一个n个点m条边的无向图,问是否有一种选出一些边的方式使得所有点的度数都是奇数。

注释:$1\le n \le 5\cdot 10^4$,$1\le m\le 10^5$。


想法

结论题:对于一个联通块来讲,如果求出它的生成树。只考虑生成树上的边的选取情况是否可能即是这个联通块的答案。

证明:如果存在一种,选取生成树以外的边满足题意,我们可以将这条边覆盖的树边全部取反,将该边舍去,仍然满足题意。

故此,用并查集求出生成树,然后在上面跑树形dp即可。

最后,附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 50010
#define M 100010
using namespace std;
int head[N],to[N<<1],nxt[N<<1],val[N<<1],cnt;
int is[M],tot,n,m,fa[N],f[N],vis[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
void add(int u,int v,int w) {to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;}
void dfs(int pos,int fa)
{
int now=0; vis[pos]=1;
for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)
{
dfs(to[i],pos);
if(f[to[i]]) now++;
else is[val[i]]=1,tot--;
}
f[pos]=!(now&1);
}
int main()
{
n=rd(),m=rd(); tot=m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int x=rd(),y=rd();
int dx=find(x),dy=find(y);
if(dx!=dy) add(x,y,i),add(y,x,i),fa[dx]=dy;
else is[i]=1,tot--;
}
for(int i=1;i<=n;i++) if(!vis[i])
{
dfs(i,0); if(f[i]) {puts("-1"); return 0;}
}
printf("%d\n",tot);
for(int i=1;i<=m;i++) if(!is[i]) printf("%d\n",i);
return 0;
}

小结:好题啊,真心好题。首先这个结论不是想Gem那样没法猜的结论,这个结论是可以证出来的。其次树形dp很常规啊!