Gotta Write A Code

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

posts - 33, comments - 33, trackbacks - 0

<

2011年9月

>

日

一

二

三

四

五

六

28

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

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

搜索

閱讀排行榜

評論排行榜

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 閱讀(1553) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜