• <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 - 12,  comments - 16,  trackbacks - 0
            問題描述:
                  
            給定一個無向圖G,一條路徑經過圖G的每一條邊,且僅經過一次,這條路徑稱為歐拉路徑(Eulerian Tour),如果歐拉路徑的起始頂點和終點是同一頂點,則稱為歐拉回路(Eulerian circuit).
                
            算法:
               
            無向圖G存在歐拉路徑的充要條件:G是連通的,且至多除兩個點外(可以為0,連接圖不可能有且僅有一個頂點的度為奇數)其它所有頂點的度為偶數.
               
            無向圖G存在歐拉回路的充要條件:G是連通的且所有頂點的度為偶數;
                
            算法描述:
                
             1 tour: 數組,用于存儲歐拉路徑,反序輸出即為歐拉路徑
             2 pos: int      
             3 
               find_eulerian_circuit()      
             4 {             
             5     pos=0;            
             6     find_circuit(1);      
             7 }     
             8 
               find_eulerian_tour()     
             9 {            
            10    find a vertex i ,the degree of which is odd           
            11    pos=0;            
            12    find_circuit(i);    
            13 }      
            14 
               find_circuit(vertex i)      
            15 {         
            16     while(exist j,(i,j) is the edge of G)          
            17     {               
            18        remove edge(i,j);                
            19        find_circuit(j);           
            20     }            
            21     tour[pos++]=i;      
            22 
            23 
             

             USACO  3.2 Riding the fence,就是一個求歐拉路徑的問題.
             
            問題描述:    

            Farmer John owns a large number of fences that must be repaired annually. He traverses the fences by riding a horse along each and every one of them (and nowhere else) and fixing the broken parts.

            Farmer John is as lazy as the next farmer and hates to ride the same fence twice. Your program must read in a description of a network of fences and tell Farmer John a path to traverse each fence length exactly once, if possible. Farmer J can, if he wishes, start and finish at any fence intersection.

            Every fence connects two fence intersections, which are numbered inclusively from 1 through 500 (though some farms have far fewer than 500 intersections). Any number of fences (>=1) can meet at a fence intersection. It is always possible to ride from any fence to any other fence (i.e., all fences are "connected").

            Your program must output the path of intersections that, if interpreted as a base 500 number, would have the smallest magnitude.

            There will always be at least one solution for each set of input data supplied to your program for testing.

            PROGRAM NAME: fence

            INPUT FORMAT

            Line 1:

            The number of fences, F (1 <= F <= 1024)

            Line 2..F+1:

            A pair of integers (1 <= i,j <= 500) that tell which pair of intersections this fence connects.

            SAMPLE INPUT (file fence.in)

            9

            1 2

            2 3

            3 4

            4 2

            4 5

            2 5

            5 6

            5 7

            4 6

            OUTPUT FORMAT

            The output consists of F+1 lines, each containing a single integer. Print the number of the starting intersection on the first line, the next intersection's number on the next line, and so on, until the final intersection on the last line. There might be many possible answers to any given input set, but only one is ordered correctly.

            SAMPLE OUTPUT (file fence.out)

            1

            2

            3

            4

            2

            5

            4

            6

            5

            7

               解答:簡單的歐拉路徑問題,圖采用鄰接表存儲,附原碼

              
            /*
            ID: kuramaw1
            PROG: fence
            LANG: C++
            */

            #include 
            <fstream>

            using std::ifstream;
            using std::ofstream;
            using std::endl;

            #ifdef _DEBUG
            #include 
            <iostream>
            using std::cout;
            #endif

            #define  MAX_V 500
            #define  MAX_EDGE 1025

            #define  MAX(a,b) ((a)>(b)?(a):(b))

            struct grapha
            {
                
            struct node
                {
                    
            short v;
                    node 
            * next;
                    node(
            const short _v=-1):v(_v),next(NULL)
                    {

                    }
                    
                };

                
            struct ver
                {
                    node 
            * r;
                    
            short d;//degree
                    ver():d(0)
                    {
                        r
            =new node();

                    }
                    
            ~ver()
                    {
                        node 
            * n=r;
                        
            while(n!=NULL)
                        {
                            node 
            * t=n;
                            n
            =n->next;
                            delete t;
                        }
                    }
                    inline 
            void add_neighbor(const short &v)
                    {
                        node 
            * t=new node(v);
                        node 
            * p=r;
                        node 
            * n=p->next;
                        
            while(n!=NULL && v>n->v)
                        {
                            p
            =n;
                            n
            =n->next;
                        }
                        p
            ->next=t;
                        t
            ->next=n;
                        d
            ++;
                    }
                    inline 
            void  remove_neighbor(const short &v)
                    {
                        node 
            * p=r;
                        node 
            * n=p->next;
                        
            while(n!=NULL && v!=n->v)
                        {
                            p
            =n;
                            n
            =n->next;
                        }
                        
            if(n!=NULL)
                        {
                            p
            ->next=n->next;
                            delete n;
                            d
            --;
                        }

                    }
                };

                ver v[MAX_V];
                
            short n;
                
            short * tour;
                
            short pos;

                grapha():n(
            0),tour(NULL)
                {

                }

                
            void add_edge(const short  &_u,const short &_v)
                {
                    v[_u
            -1].add_neighbor(_v-1);
                    v[_v
            -1].add_neighbor(_u-1);
                    
            short t=MAX(_u,_v);
                    
            if(t>n)
                        n
            =t;
                }

                
            void find_tour(const short &s)
                {
                        
            while(v[s].d>0)
                        {
                            
            short j=v[s].r->next->v;
                            v[s].remove_neighbor(j);
                            v[j].remove_neighbor(s);
                            find_tour(j);
                        }
                        tour[pos
            ++]=s+1;

                }

                
            void Eulerian_tour(short * _tour)
                {
                    tour
            =_tour;
                    pos
            =0;
                    
            bool b=false;
                    
            for(int i=0;i<n;i++)
                     
            if(v[i].d % 2!=0)
                     {
                         find_tour(i);
                         b
            =true;
                         
            break;
                     }
                   
            if(!b)
                       find_tour(
            0);

                }


            };

            grapha g;
            short tour[MAX_EDGE];
            short f;
            int main()
            {
                ifstream 
            in("fence.in");
                
            in>>f;
                
            for(short i=0;i<f;i++)
                {
                    
            short u,v;
                    
            in>>u>>v;
                    g.add_edge(u,v);
                }

                
            //do
                g.Eulerian_tour(tour);



                
            //out
                ofstream out("fence.out");
                
            for(int i=f;i>=0;i--)
                 
            out<<tour[i]<<endl;
                
            out.close();
            }

                
            posted on 2009-08-12 21:18 kuramawzw 閱讀(598) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            <2009年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(5)

            隨筆分類

            隨筆檔案

            文章檔案

            Algorithm

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国内精品久久久久久久涩爱| 2021国内久久精品| 亚洲AV日韩精品久久久久久| 久久无码人妻精品一区二区三区| 国产精品久久毛片完整版| 无码人妻少妇久久中文字幕蜜桃| 久久乐国产综合亚洲精品| 久久99亚洲综合精品首页| 亚洲国产精品婷婷久久| 国产精品日韩欧美久久综合| 香蕉久久一区二区不卡无毒影院| 99国产精品久久| 久久精品国产一区| 国产精品成人久久久久久久| 四虎国产精品免费久久5151 | 精品久久久久久无码人妻热| 九九99精品久久久久久| 99精品国产在热久久无毒不卡| 亚洲国产美女精品久久久久∴| 久久精品国产色蜜蜜麻豆| 中文字幕久久精品无码| 成人国内精品久久久久一区| 久久99国产精一区二区三区| 岛国搬运www久久| 亚洲一级Av无码毛片久久精品| 国内精品久久久久影院老司| 久久WWW免费人成一看片| 久久国产精品成人片免费| 四虎国产精品免费久久久| 久久国产精品免费一区| 国产精品久久新婚兰兰| 久久精品人人做人人爽97| 国产福利电影一区二区三区,免费久久久久久久精 | 国产亚洲婷婷香蕉久久精品| 国产精品成人精品久久久| 亚洲精品无码久久久| 精品久久久久久无码中文字幕一区| 久久最新精品国产| 怡红院日本一道日本久久| 久久无码AV中文出轨人妻| …久久精品99久久香蕉国产|