POJ 2513 【字典树】【欧拉回路】
2024-09-06 13:26:20
题意:
有很多棒子,两端有颜色,告诉你两端的颜色,让你把这些棒子拼接起来要求相邻的接点的两个颜色是一样的。
问能否拼接成功。
思路:
将颜色看作节点,将棒子看作边,寻找欧拉通路。
保证图的连通性的时候用到并查集。
这里颜色由于是字符串代替,所以需要用到字典树优化离散化过程。
字典树的学习感谢博客http://www.ahathinking.com/archives/14.html
重点是这个图很棒:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<iostream>
#include<stdlib.h>
using namespace std;
int me[*+];
int out[];
struct ti
{
void add(char *,int);
int findi(char *);
ti *mine[];
int num;
};
void ti::add(char *s,int tmp)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
next->mine[s[i]-]=(ti*)malloc(sizeof(ti));
memset(next->mine[s[i]-]->mine,NULL,sizeof(mine));
next->mine[s[i]-]->num=;
}
next=next->mine[s[i]-];
}
next->num=tmp;
}
int ti::findi(char *s)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
return ;
}
next=next->mine[s[i]-];
}
return next->num;
}
ti tree;
int findme(int n)
{
if(n!=me[n])
return me[n]=findme(me[n]);
return n;
}
int main()
{
memset(tree.mine,NULL,sizeof(tree.mine));
tree.num=;
char col1[],col2[];
for(int i=;i<=;i++)
{
me[i]=i;
}
int num=;
while(scanf("%s%s",col1,col2)!=EOF)
{
if(tree.findi(col1)==)
{
num++;
tree.add(col1,num);
}
if(tree.findi(col2)==)
{
num++;
tree.add(col2,num);
}
int tmpa=findme(tree.findi(col1));
int tmpb=findme(tree.findi(col2));
if(tmpa!=tmpb)
me[tmpb]=tmpa;
out[tree.findi(col1)]++;
out[tree.findi(col2)]++;
}
int c=;
int x,y,z;
x=y=z=;
for(int i=;i<=num;i++)
{
if(me[i]==i)
c++;
if(out[i]&)
x++;
}
if(x==||c>||x>)
printf("Impossible\n");
else
printf("Possible\n");
}
最新文章
- 数据库设计中的Soft Delete模式
- iMac 升级到10.12后,蓝牙不能用
- 项目vue2.0仿外卖APP(二)
- 【数论】X problem
- ios打包
- 洛谷P2015 二叉苹果树
- Beaglebone Black的启动
- Smarty 变量使用
- listview前几个item的图片怎么是空白的、listview更新了ui不起作用、在handler里更新了UI不起作用
- python mysql 2014 Commands out of sync; you can&#39;t run this command now
- 【java】控制台实现贪吃蛇小游戏-LinkedList、Scanner
- git rejected - non-fast-forward
- SecureCRT的安装与破解(过程很详细!!!)
- MFC项目中:报错:“fatal error LNK1561: 必须定义入口点”解决方法
- 使用Metasploit渗透攻击windows系统(一)
- asp.net core mvc 中间件之WebpackDevMiddleware
- 前端开发笔记(2)css基础(上)
- dtcp格式定义
- Luogu 1070 道路游戏
- ubuntu16更新源