奇数度数 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很常规啊！

巴特西

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

奇数度数 bzoj-2443 Usaco-2011 Open

最新文章

热门文章