• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        




            
	
		
            
			


            
posts - 33, 
comments - 33, 
trackbacks - 0


            
	

            


            
	
					


            
	
	題意：如果單詞A的結(jié)尾字母與單詞B的首字母相同，那么可以認(rèn)為是A到B相通。給出一系列單詞，求這些詞按照某種排列能否串通。
            題解：
            如果直接按照題意建模，以單詞為頂點，邊表示兩兩相通，那么將會得到哈密頓回路模型。顯然是很難解的。
            換一種方式，以字母為頂點，邊表示傳送的單詞，那么就得到歐拉回路模型的圖，可以按照歐拉定理求解。
            以下給出Euler圖的相關(guān)知識：
            Euler回路：G中經(jīng)過每條邊一次且僅一次的回路
            Euler路徑：G中經(jīng)過每條邊一次且僅一次的路徑
            無向圖存在Euler回路定理：當(dāng)它是連通圖+頂點度數(shù)為偶數(shù)
            無向圖存在Euler路徑定理：當(dāng)它是連通圖+除兩個頂點度為奇數(shù)外，其余為偶數(shù)
            有向圖存在Euler回路定理：當(dāng)它是連通圖+頂點入度 == 出度
            有向圖存在Euler路徑定理：當(dāng)它是連通圖+除一個頂點的入度和出度的差的絕對值小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 閱讀(1543) 評論(0)  編輯 收藏 引用  
            

            







            
	    
    




            



            


            

	
            
		
		
            只有注冊用戶登錄后才能發(fā)表評論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				

            




    
    







            
	   
	



国产精品免费看久久久|
久久久久免费看成人影片|
99精品久久久久久久婷婷|
久久免费精品一区二区|
老司机午夜网站国内精品久久久久久久久
|
久久精品aⅴ无码中文字字幕重口
久久精品a亚洲国产v高清不卡
|
久久精品国产99国产电影网|
精品少妇人妻av无码久久|
91精品久久久久久无码|
青青草原综合久久大伊人|
AV狠狠色丁香婷婷综合久久|
精品久久人人妻人人做精品|
久久精品国产乱子伦|
99久久精品九九亚洲精品|
国产毛片欧美毛片久久久|
青青青国产精品国产精品久久久久
|
一本色道久久88精品综合|
老司机国内精品久久久久|
午夜人妻久久久久久久久|
国产精品免费福利久久|
最新久久免费视频|
久久久久久亚洲精品不卡|
久久久久中文字幕|
久久久久亚洲AV成人片|
国产aⅴ激情无码久久|
久久综合色区|
久久播电影网|
欧美激情精品久久久久|
国产亚洲婷婷香蕉久久精品|
久久久久亚洲av无码专区导航
|
欧美黑人又粗又大久久久|
国内精品久久久久影院优|
人妻无码αv中文字幕久久琪琪布
人妻无码精品久久亚瑟影视
|
国产69精品久久久久777|
久久妇女高潮几次MBA|
亚洲精品乱码久久久久久不卡|
久久se精品一区二区|
欧美久久综合性欧美|
亚洲成色999久久网站|
青青青青久久精品国产|
国产精品成人久久久久三级午夜电影|