• <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>
            隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
            數(shù)據(jù)加載中……

            Pku 1632 Vase Collection (Dfs)

            問題描述:
            給定一些關(guān)系,是個(gè)二分圖,要求它的最大完美匹配。
            解題思路:
            枚舉左邊的點(diǎn),對任意一個(gè)點(diǎn)枚舉它的邊子集,再在枚舉到的邊子集的右邊點(diǎn)集中以相同方式枚舉,最后形成左右兩邊均為K的點(diǎn),檢測是否為完全二分圖即可。

            代碼如下:
            #include <iostream>
            #include 
            <vector>
            using namespace std;

            int t;
            int n, i;

            vector 
            < int > lvec[40], rvec[40];
            int l, r, dep;
            int bo[40], Max;

            struct Stack
            {
                
            int a[100];
                
            int top;
            }
            Left, Right;

            int map[40][40];


            //檢查給定圖是否是K-完美匹配圖(這里K == Left.top)
            int Process()
            {
                
            int i, j;
                
            //Stack Left
                
            //Stack Right
                
            //檢查兩個(gè)棧中是否有完全邊,即K*K條邊

                
            for(i = 0; i < Left.top; i++)
                
            {
                    
            for(j = 0; j < Right.top; j++)
                    
            {
                        
            if(!map[ Right.a[j] ][ Left.a[i] ])
                            
            return 0;
                    }

                }


                
            return 1;
            }



            //對右邊的第一個(gè)被左邊點(diǎn)枚舉到的點(diǎn)進(jìn)行枚舉,枚舉它的邊子集
            int rdfs(int u, int index)
            {
                
            int i, size = rvec[u].size();

                
            if(size < Left.top)
                    
            return 0;

                
            if(Right.top > Left.top)
                    
            return 0;

                
            if(Left.top == Right.top)
                
            {
                    
            if( Process() )
                        
            return 1;
                }


                
            for(i = index; i < size; i++){
                    Right.a[ Right.top
            ++ ] = rvec[u][i];
                    
            if( rdfs(u, i+1) )
                        
            return 1;
                    Right.top 
            --;
                }

                
            return 0;
            }


            //左邊任選一個(gè)點(diǎn)枚舉他的邊子集

            void ldfs(int u, int index)
            {
                
            int i, size = lvec[u].size();

                
            if(Left.top > 10)
                    
            return ;

                Right.top 
            = 0;


                
            if(Left.top > Max && rdfs(Left.a[0], 0) )
                
            {
                    
            if(Left.top > Max)
                        Max 
            =  Left.top;
                }


                
            for(i = index; i < size; i++){
                    Left.a[ Left.top
            ++ ] = lvec[u][i];
                    ldfs(u, i
            +1);
                    Left.top 
            --;
                }

            }


            int main()
            {
                
            int i, j;
                scanf(
            "%d"&t);

                
            while(t--)
                
            {
                    Max 
            = 0;
                    scanf(
            "%d"&n);

                    memset(map, 
            0sizeof(map));

                    
            for(i = 1; i <= 36; i++)
                    
            {
                        lvec[i].clear();
                        rvec[i].clear();
                    }


                    memset( bo, 
            0sizeof(bo) );

                    
            for(i = 0; i < n; i++)
                    
            {
                        scanf(
            "%d %d"&l, &r);
                        map[l][r] 
            = 1;
                        bo[ l ] 
            = 1;
                    }


                    
            for(i = 1; i <= 36; i++){

                        
            for(j = 1; j <= 36; j++){

                            
            if(map[i][j])
                            
            {
                                lvec[i].push_back( j );
                                rvec[j].push_back( i );
                            }

                        }

                    }


                    
            for(i = 1; i <= 36; i++)
                    
            {
                        
            if(bo[i]){
                            Left.top 
            = 0;
                            ldfs(i, 
            0);
                        }

                    }

                    printf(
            "%d\n", Max);
                }

            }

            posted on 2009-02-15 21:15 英雄哪里出來 閱讀(415) 評論(0)  編輯 收藏 引用 所屬分類: ACM

            久久精品国产亚洲av高清漫画| 久久亚洲春色中文字幕久久久| 久久精品国产亚洲沈樵| 久久久久夜夜夜精品国产| 日本一区精品久久久久影院| 久久国产精品二国产精品| 久久亚洲2019中文字幕| 国产激情久久久久久熟女老人 | 精品久久久久久国产三级| 亚洲欧美国产精品专区久久 | 日本道色综合久久影院| 色欲综合久久躁天天躁| 国产精品久久久久影视不卡| 日韩va亚洲va欧美va久久| 欧美黑人又粗又大久久久| 国产亚洲精午夜久久久久久 | 无码国内精品久久人妻| 国产精品综合久久第一页| 伊人久久久AV老熟妇色| 99久久综合狠狠综合久久| 色综合久久综合中文综合网| 国产综合精品久久亚洲| 精品久久人妻av中文字幕| 99精品国产免费久久久久久下载 | 欧美精品国产综合久久| 99久久国产主播综合精品| 浪潮AV色综合久久天堂| 人妻无码精品久久亚瑟影视| 久久精品国产亚洲一区二区三区| 国内精品久久久久伊人av| 波多野结衣AV无码久久一区| 手机看片久久高清国产日韩| 伊人色综合久久| 日本道色综合久久影院| 久久精品国产福利国产秒| 久久精品国产亚洲av麻豆小说| 精品国产乱码久久久久软件| 久久久久亚洲国产| 久久精品国产99国产精品导航 | 日韩精品久久久久久久电影蜜臀| 精品一二三区久久aaa片|