青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
Gotta Write A Code
C++博客
::
首頁
::
新隨筆
::
聯(lián)系
::
聚合
::
管理
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: 作品:動態(tài)語言AnyC 1.0
@so
其實里面的代碼存在bug...
--qqdy
3.?re: 作品:動態(tài)語言AnyC 1.0
游戲腳本高級編程的代碼很好啊。
--so
4.?re: 作品:動態(tài)語言AnyC 1.0
仰慕!!我剛開始學習編譯呢
--coreBugZJ
5.?re: AnyC:添加類型限制[未登錄]
Orz!!
--diryboy
閱讀排行榜
1.?逆序數(shù)及其求法(10803)
2.?Poj 3310 判環(huán)+度(6004)
3.?水文一篇--基于CUDA的矩陣相乘(4641)
4.?Poj2010 - 堆的應(yīng)用(2498)
5.?水文:淺析PE File(2379)
評論排行榜
1.?作品:動態(tài)語言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的結(jié)尾字母與單詞B的首字母相同,那么可以認為是A到B相通。給出一系列單詞,求這些詞按照某種排列能否串通。
題解:
如果直接按照題意建模,以單詞為頂點,邊表示兩兩相通,那么將會得到哈密頓回路模型。顯然是很難解的。
換一種方式,以字母為頂點,邊表示傳送的單詞,那么就得到歐拉回路模型的圖,可以按照歐拉定理求解。
以下給出Euler圖的相關(guān)知識:
Euler回路:G中經(jīng)過每條邊一次且僅一次的回路
Euler路徑:G中經(jīng)過每條邊一次且僅一次的路徑
無向圖存在Euler回路定理:當它是連通圖+頂點度數(shù)為偶數(shù)
無向圖存在Euler路徑定理:當它是連通圖+除兩個頂點度為奇數(shù)外,其余為偶數(shù)
有向圖存在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
閱讀(1550)
評論(0)
編輯
收藏
引用
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Powered by:
C++博客
Copyright ©2025 bennycen
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
国产伦精品一区二区三
|
久久成人精品
|
国产精品丝袜xxxxxxx
|
欧美网站在线
|
国产精品视频不卡
|
国产欧美精品
|
在线观看福利一区
|
亚洲三级国产
|
亚洲一区二区黄
|
久久九九久久九九
|
欧美国产视频在线观看
|
欧美激情二区三区
|
亚洲精选一区
|
亚洲欧美日韩视频二区
|
久久精品国产亚洲一区二区三区
|
欧美一区二区福利在线
|
免费日韩视频
|
美日韩精品免费
|
在线免费高清一区二区三区
|
91久久久亚洲精品
|
在线一区二区三区四区五区
|
性伦欧美刺激片在线观看
|
久久久一区二区
|
亚洲精品一区二区三区婷婷月
|
亚洲一区日本
|
欧美福利一区二区
|
国产亚洲va综合人人澡精品
|
日韩视频永久免费
|
久久成人人人人精品欧
|
亚洲国产成人av好男人在线观看
|
欧美国产精品人人做人人爱
|
一区二区三区国产盗摄
|
美女国内精品自产拍在线播放
|
欧美揉bbbbb揉bbbbb
|
在线观看国产一区二区
|
性色av一区二区三区
|
91久久嫩草影院一区二区
|
久久精品理论片
|
国产精品美女久久久久久免费
|
亚洲欧洲视频在线
|
久久影院午夜片一区
|
亚洲午夜av
|
欧美日韩成人在线
|
亚洲激情视频在线观看
|
老司机成人网
|
欧美一级在线亚洲天堂
|
欧美午夜a级限制福利片
|
91久久亚洲
|
免费高清在线视频一区·
|
亚洲伊人观看
|
国产精品国产三级国产a
|
夜夜狂射影院欧美极品
|
亚洲国产精品久久91精品
|
久久人人爽国产
|
韩日视频一区
|
久久久福利视频
|
亚洲欧美电影院
|
国产精品亚洲综合
|
亚洲欧美中文另类
|
亚洲一区3d动漫同人无遮挡
|
欧美图区在线视频
|
亚洲一区二区三区涩
|
9色精品在线
|
国产精品成av人在线视午夜片
|
夜夜嗨av一区二区三区免费区
|
91久久国产综合久久蜜月精品
|
亚洲视频免费
|
99在线精品观看
|
国产精品国产三级国产aⅴ浪潮
|
宅男精品导航
|
国产精品99久久久久久久久久久久
|
欧美午夜www高清视频
|
国产乱肥老妇国产一区二
|
国产精品一二三
|
欧美在线高清视频
|
欧美一进一出视频
|
国产一区二区三区久久久
|
久久久久久午夜
|
久久亚洲国产精品一区二区
|
亚洲国产美女
|
日韩视频在线你懂得
|
国产精品视频精品
|
久久免费高清
|
欧美黄色片免费观看
|
亚洲一区一卡
|
久久精品视频导航
|
亚洲乱码国产乱码精品精
|
亚洲图片欧美日产
|
永久免费精品影视网站
|
亚洲精品视频免费
|
欧美午夜寂寞影院
|
久久精品午夜
|
欧美金8天国
|
欧美自拍偷拍午夜视频
|
榴莲视频成人在线观看
|
亚洲欧美日韩国产综合精品二区
|
欧美freesex8一10精品
|
欧美日本精品
|
久久久久久综合
|
欧美区亚洲区
|
久久精品2019中文字幕
|
欧美激情视频一区二区三区免费
|
午夜精品婷婷
|
欧美区二区三区
|
猫咪成人在线观看
|
国产精品社区
|
亚洲人成亚洲人成在线观看图片
|
国产欧美精品日韩区二区麻豆天美
|
欧美成黄导航
|
国产午夜精品美女视频明星a级
|
欧美中在线观看
|
日韩网站在线
|
久久久久国内
|
午夜精品久久久久久久99水蜜桃
|
亚洲国产成人porn
|
国产亚洲欧美一区二区三区
|
欧美.www
|
国产一区二区三区免费不卡
|
欧美日韩另类丝袜其他
|
久久亚洲精品一区二区
|
欧美视频一区二区三区四区
|
欧美激情一区二区久久久
|
黑人操亚洲美女惩罚
|
亚洲一区二区视频在线
|
一区二区欧美激情
|
欧美精品aa
|
欧美激情va永久在线播放
|
另类专区欧美制服同性
|
99精品欧美
|
亚洲国产精品久久久久婷婷884
|
亚洲天堂av在线免费
|
亚洲片国产一区一级在线观看
|
欧美在线观看视频在线
|
欧美在线网站
|
国产麻豆午夜三级精品
|
中文在线一区
|
亚洲欧美精品在线观看
|
国产精品久久久久久久久动漫
|
久久三级福利
|
国产一区二区三区成人欧美日韩在线观看
|
99国产精品久久久久久久久久
|
日韩视频一区二区
|
欧美精品在线一区二区
|
日韩亚洲一区二区
|
亚洲精品一区二区三区av
|
欧美成va人片在线观看
|
亚洲国产毛片完整版
|
国产日韩在线一区
|
亚洲综合首页
|
久久久夜夜夜
|
91久久精品日日躁夜夜躁国产
|
欧美18av
|
亚洲人成人一区二区在线观看
|
一区二区免费在线视频
|
欧美日在线观看
|
亚洲欧美一区二区三区久久
|
亚洲欧美国产三级
|
国产欧美亚洲视频
|
久久久夜精品
|
欧美激情小视频
|
亚洲视频碰碰
|
国产视频一区免费看
|
久久久久高清
|
亚洲国产一区二区a毛片
|
日韩五码在线
|
国产精品视频一二三
|
久久久久国内
|
99国产精品99久久久久久粉嫩
|
欧美在线一区二区
|
亚洲国产精品福利
|
国产精品红桃
|
久久久久久夜
|
夜夜爽www精品
|
久久久久一区二区三区四区
|
亚洲人成网站在线观看播放
|
国产精品美女久久久久久久
|
久久综合网络一区二区
|
宅男噜噜噜66一区二区66
|
久久亚洲影音av资源网
|
日韩视频在线观看
|
国产亚洲精品久
|
欧美精品激情在线观看
|
香蕉久久国产
|
日韩小视频在线观看专区
|
快播亚洲色图
|
欧美在线精品免播放器视频
|
99这里只有久久精品视频
|
海角社区69精品视频
|
国产精品美女久久久久久久
|
在线欧美福利
|
欧美日韩中文在线观看
|
久久久久久久久综合
|
亚洲一区二区综合
|
亚洲国产高清一区二区三区
|
午夜精品亚洲一区二区三区嫩草
|
亚洲黄色大片
|
国内揄拍国内精品少妇国语
|
国产精品久久一区二区三区
|
欧美高清你懂得
|
久久国产精品久久久久久
|