首页 > 学院 > 开发设计 > 正文

[poj 2513] Colored Sticks (trie+欧拉路)

2019-11-08 18:52:42
字体:
来源:转载
供稿:网友

题目大意:给定一些木棒,木棒两端都涂上颜色,求是否能将木棒首尾相接,连成一条直线,要求不同木棒相接的一边必须是相同颜色的。

我们把颜色看做点,木棒看做边,这道题就转为了求是否存在欧拉路。

而判断欧拉路只要看两点 ①图连通 ②所有节点的度为偶数或只有两个奇数度节点。

判断①我们可以使用并查集且必须压缩路径,否则会超时。而并查集需要利用数组下标,但读入为字符串,并且有25w条边,使用hash会超时。

这时候我们可以用trie(字典树),关于字典树可以自行百度。

#include <cstdio>#include <iostream>#include <cstring>#define maxn 500000using namespace std;struct Trie{	Trie* next[27];	bool flag;	int id;	Trie()    {        flag=false;        id=0;        memset(next,0,sizeof(next));    } }root;int tot;int dg[maxn+5];int fa[maxn+5];int trie(char *ch){	Trie* tree=&root;	int len=0;	while (ch[len]!='/0')	{		int pub=ch[len++]-'a';		if (!tree->next[pub]) tree->next[pub]=new Trie();		tree=tree->next[pub];	}	if (tree->flag) return tree->id;	else 	{		tree->flag=true;		tree->id=++tot;		return tree->id=tot;	}}int getf(int x){	if (fa[x]!=x) fa[x]=getf(fa[x]);	return fa[x];}void ice_chair(int x,int y){	int fx=getf(y);	int fy=getf(x);	fa[fy]=fx;	return ;}char a[15],b[15];int main(){	register int i,j;	for (i=1;i<=maxn;i++)	{		fa[i]=i;	}	while(cin>>a>>b)	{		int x=trie(a);		int y=trie(b);		dg[x]++;		dg[y]++;		ice_chair(x,y);	}	int s=getf(1);	int ans=0;	for (i=1;i<=tot;i++)	{		if (dg[i]%2==1) ans++;		if (ans>2)		{			PRintf("Impossible");			return 0;		}		if (getf(i)!=s)		{			printf("Impossible");			return 0;			}	}	if (ans==1) printf("Impossible");	else printf("Possible");	return 0;}


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表