[福建集训2011][LOJ10111]相框

这题主要还是分类讨论欧拉回路

首先对于导线一端没有东西的新建一个节点由于原图不一定连通所以需要用到并查集判断有多少个连通块将一条导线连接的两个焊点连接

然后先对于只有一个连通块考虑

1.如果一个焊点是孤立点它对于导线无影响跳过

2.如果一个焊点度数大于2 它必须被烧熔

3.对于每两对奇点它们必须相连这样才满足欧拉回路

对于一个连通块处理后考虑多个连通块，必须把他们组合在一起

1.同样忽略孤立点

**2.如果原图是一个环 **

**需要找到一个点将其烧熔,才能继续组合 **

但其中若有焊点度数大于2,那么它本身已经被烧熔了所以可以略去此步

最后每个连通块向外和另一连通块连接一根导线就组装好了

3.原图有链这种情况下只要将一对奇点向外连就好了当然对于程序来说就是无需考虑有链的连通块连接的答案，以为这之前单个处理已经统计过了

#include<bits/stdc++.h>

using namespace std;

const int maxn=101005;

int tot,ans,n,m,a,b,cnt;

int d[maxn],flag1[maxn],flag2[maxn],fa[maxn];

int read()

{

	int ch=0,x=0;while(ch=getchar(),ch<'0'||ch>'9');

	while(x=x*10+ch-48,ch=getchar(),ch>='0'&&ch<='9');

	return x;

}

int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}

void conn(int x,int y)

{

	int fxx=getfa(x),fyy=getfa(y);

	if(fxx!=fyy)fa[fxx]=fyy;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;i++)fa[i]=i;

	for(int i=1;i<=m;i++)

	{

		a=read();b=read();

		if(!a) a=++n,fa[a]=a;

		if(!b) b=++n,fa[b]=b;

		conn(a,b);d[a]++;d[b]++;

	}

	for(int i=1;i<=n;i++)

	{

		if(!d[i])continue;

		if(d[i]&1)

		{

			cnt++;

			flag1[getfa(i)]=1;

		}

		if(d[i]>2)

		{

			ans++;

			flag2[getfa(i)]=1;

		}

	}

	for(int i=1;i<=n;i++)

	if(getfa(i)==i&&d[i])tot++;

	if(tot>1)

	{

		for(int i=1;i<=n;i++)

		if(getfa(i)==i&&d[i]&&!flag1[i])

		{

			ans++;

			if(!flag2[i])ans++;

		}

	}

	ans+=cnt/2;

	printf("%d",ans);

	return 0;

}

巴特西

[福建集训2011][LOJ10111]相框

最新文章

热门文章