Gotta Write A Code
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
posts - 33, comments - 33, trackbacks - 0
<
2011年6月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(5)
给我留言
查看公开留言
查看私人留言
随笔分类
CUDA(1)
Windows Programming(4)
算法题解(22)
随笔档案
2012年5月 (1)
2012年3月 (9)
2011年11月 (4)
2011年10月 (1)
2011年9月 (1)
2011年7月 (1)
2011年6月 (3)
2011年5月 (1)
2011年4月 (1)
2011年3月 (2)
2011年1月 (2)
2010年12月 (1)
2010年11月 (6)
搜索
最新评论
1. re: DX笔记[未登录]
OrOrOrz!!
--diryboy
2. re: 作品:动态语言AnyC 1.0
@so
其实里面的代码存在bug...
--qqdy
3. re: 作品:动态语言AnyC 1.0
游戏脚本高级编程的代码很好啊。
--so
4. re: 作品:动态语言AnyC 1.0
仰慕!!我刚开始学习编译呢
--coreBugZJ
5. re: AnyC:添加类型限制[未登录]
Orz!!
--diryboy
阅读排行榜
1. 逆序数及其求法(10741)
2. Poj 3310 判环+度(5965)
3. 水文一篇--基于CUDA的矩阵相乘(4600)
4. Poj2010 - 堆的应用(2466)
5. 水文:浅析PE File(2329)
评论排行榜
1. 作品:动态语言AnyC 1.0(4)
2. poj 3074(3)
3. ACM/ICPC杭州站 - hdu3680(3)
4. 水题四道 3-30(3)
5. POJ Challenge - 2011.04.10部分题解(3)
Poj 1386 欧拉回路
题意:如果单词A的结尾字母与单词B的首字母相同,那么可以认为是A到B相通。给出一系列单词,求这些词按照某种排列能否串通。
题解:
如果直接按照题意建模,以单词为顶点,边表示两两相通,那么将会得到哈密顿回路模型。显然是很难解的。
换一种方式,以字母为顶点,边表示传送的单词,那么就得到欧拉回路模型的图,可以按照欧拉定理求解。
以下给出Euler图的相关知识:
Euler回路:G中经过每条边一次且仅一次的回路
Euler路径:G中经过每条边一次且仅一次的路径
无向图存在Euler回路定理:当它是连通图+顶点度数为偶数
无向图存在Euler路径定理:当它是连通图+除两个顶点度为奇数外,其余为偶数
有向图存在Euler回路定理:当它是连通图+顶点入度 == 出度
有向图存在Euler路径定理:当它是连通图+除一个顶点的入度和出度的差的绝对值小1外,其余相等
代码:
#include
<
stdio.h
>
#include
<
string
.h
>
const
int
N
=
30
;
class
UnionSet
{
private
:
int
parent[N];
int
rank[N];
int
size;
public
:
UnionSet(
int
_size):size(_size)
{
init();
}
~
UnionSet()
{
}
void
init()
{
for
(
int
i
=
0
; i
<
size;
++
i)
{
parent[i]
=
-
1
;
rank[i]
=
1
;
}
}
int
root(
int
_x)
{
int
r
=
_x;
while
(parent[r]
>=
0
)
r
=
parent[r];
int
i
=
_x;
int
j;
while
(parent[i]
>=
0
)
{
j
=
parent[i];
parent[i]
=
r;
i
=
j;
}
return
r;
}
int
Union(
int
_r1,
int
_r2)
{
if
(_r1
==
_r2)
return
_r1;
else
{
int
root1
=
root(_r1);
int
root2
=
root(_r2);
if
(root1
==
root2)
return
root1;
if
(rank[root1]
>
rank[root2])
{
parent[root2]
=
root1;
rank[root1]
+=
rank[root2];
}
else
{
parent[root1]
=
root2;
rank[root2]
+=
rank[root1];
}
}
}
int
getRank(
int
_x)
{
return
rank[_x];
}
}
;
char
buf1[
1024
];
void
Test()
{
int
In[
30
]
=
{
0
}
;
int
Out[
30
]
=
{
0
}
;
bool
visited[
30
]
=
{
false
}
;
UnionSet Set(
28
);
int
n;
scanf(
"
%d
"
,
&
n);
bool
flag
=
false
;
int
start
=
0
;
for
(
int
i
=
0
; i
<
n;
++
i)
{
scanf(
"
%s
"
,buf1);
int
len
=
strlen(buf1);
Set.Union(buf1[
0
]
-
'
a
'
,buf1[len
-
1
]
-
'
a
'
);
In[buf1[len
-
1
]
-
'
a
'
]
++
;
Out[buf1[
0
]
-
'
a
'
]
++
;
visited[buf1[
0
]
-
'
a
'
]
=
true
;
visited[buf1[len
-
1
]
-
'
a
'
]
=
true
;
if
(
!
flag)
{
start
=
buf1[
0
]
-
'
a
'
;
flag
=
true
;
}
}
for
(
int
i
=
0
; i
<
26
;
++
i)
{
if
(i
!=
start)
{
if
(visited[i]
&&
(Set.root(start)
!=
Set.root(i)))
{
printf(
"
The door cannot be opened.\n
"
);
return
;
}
}
}
int
cntIn
=
0
;
int
cntOut
=
0
;
for
(
int
i
=
0
; i
<
26
;
++
i)
{
if
(visited[i])
{
if
(In[i]
!=
Out[i])
{
if
(In[i]
-
Out[i]
==
-
1
)
{
cntIn
++
;
}
else
if
(In[i]
-
Out[i]
==
1
)
{
cntOut
++
;
}
else
{
printf(
"
The door cannot be opened.\n
"
);
return
;
}
}
}
}
if
((cntIn
!=
cntOut)
||
((cntIn
==
cntOut)
&&
(cntIn
>
1
)))
{
printf(
"
The door cannot be opened.\n
"
);
}
else
printf(
"
Ordering is possible.\n
"
);
}
int
main()
{
//
freopen("data.txt","r",stdin);
int
tc;
scanf(
"
%d
"
,
&
tc);
for
(
int
i
=
0
; i
<
tc;
++
i)
{
Test();
}
return
0
;
}
posted on 2011-06-02 11:56
bennycen
阅读(1533)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理