• <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>

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 3189 Steady Cow Assignment 二分圖的多重匹配

            思路:

            這題完全不懂,看了這份大牛的解題報(bào)告
            http://hi.baidu.com/winterlegend/blog/item/2411981e8fd0ed6bf724e45e.html
            發(fā)現(xiàn)嗎的太牛逼了!

            首先二分圖匹配,正常情況下,都是單個(gè)單個(gè)的點(diǎn)這樣匹配、
            但是像這道題,右邊的點(diǎn)一個(gè)可以匹配好幾個(gè)左邊的點(diǎn)。也是用匈牙利算法,不過要做少少修改。

            枚舉答案的時(shí)候,有兩種方法:
            一個(gè)是移動區(qū)間的方法。復(fù)雜度O(B)。注意,只移動區(qū)間右邊的時(shí)候不用重新匹配,只需要接著上次沒匹配完的繼續(xù)匹配就行了
            一個(gè)是二分法。復(fù)雜度 O(B lgB)
            由于數(shù)據(jù)的問題,這兩種方法時(shí)間相差無幾。在 16ms 和 32ms 之間。

            #include <stdio.h>

            struct barn {
                
            int link[1024], cnt, vis, cap;
            }
            ;
            struct cow {
                
            int rank[32];
            }
            ;

            struct barn barns[32];
            struct cow cows[1024];
            int start, end, last_pos;
            int N, B, tm;

            int dfs(int c)
            {
                
            int i, j;
                
            struct barn *b;

                
            for (i = start; i <= end; i++{
                    b 
            = &barns[cows[c].rank[i]];
                    
            if (b->vis == tm)
                        
            continue;
                    b
            ->vis = tm;
                    
            if (b->cnt < b->cap) {
                        b
            ->link[b->cnt++= c;
                        
            return 1;
                    }

                    
            for (j = 0; j < b->cap; j++)
                        
            if (dfs(b->link[j])) {
                            b
            ->link[j] = c;
                            
            return 1;
                        }

                }

                
            return 0;
            }


            inline 
            void init()
            {
                
            int i;

                
            for (i = 1; i <= B; i++)
                    barns[i].cnt 
            = 0;
                last_pos 
            = 1;
            }


            inline 
            int match()
            {
                
            int i, j;

                
            for (i = last_pos; i <= N; i++{
                    tm
            ++;
                    
            if (!dfs(i))
                        
            break;
                }

                last_pos 
            = i;
                
            return i > N;
            }


            int main()
            {
                
            int i, j, ans;

                freopen(
            "e:\\test\\in.txt""r", stdin);

                scanf(
            "%d%d"&N, &B);
                
            for (i = 1; i <= N; i++)
                    
            for (j = 1; j <= B; j++)
                        scanf(
            "%d"&cows[i].rank[j]);
                
            for (i = 1; i <= B; i++)
                    scanf(
            "%d"&barns[i].cap);
                
            #if 0
                
            // O(B)
                ans = B;
                start 
            = end = 1;
                
            while (start <= B && end <= B) {
                    init();
                    
            while (end <= B && !match())
                        end
            ++;
                    
            if (end - start + 1 < ans)
                        ans 
            = end - start + 1;
                    start
            ++;
                }

            #else
                
            // O(B*lgB)
                int l, r, m;

                l 
            = 1;
                r 
            = B;
                
            while (l <= r) {
                    m 
            = (l + r) / 2;
                    
            for (start = 1; start <= B - m + 1; start++{
                        end 
            = start + m - 1;
                        init();
                        
            if (match())
                            
            break;
                    }

                    
            if (start == B - m + 2{
                        
            // failed
                        l = m + 1;
                    }
             else 
                        r 
            = m - 1;
                }

                ans 
            = r + 1;
            #endif

                printf(
            "%d\n", ans);

                
            return 0;
            }

            posted on 2010-04-26 15:34 糯米 閱讀(556) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            欧美久久一区二区三区| 久久www免费人成精品香蕉| 国产精品99久久久精品无码| 一本一本久久A久久综合精品| 精品久久久久香蕉网| 51久久夜色精品国产| 久久精品日日躁夜夜躁欧美| 麻豆精品久久精品色综合| 欧美国产成人久久精品| 久久久久亚洲AV无码永不| 久久久久无码精品| 人妻精品久久无码区| 国产高清国内精品福利99久久| 伊人久久无码中文字幕| 久久中文字幕视频、最近更新| 久久人人妻人人爽人人爽| 久久中文字幕无码专区| 国产精品久久一区二区三区| 久久久久久亚洲精品影院| 亚洲精品国产成人99久久| 久久精品国产亚洲AV无码偷窥| 久久久国产精品| 97精品国产97久久久久久免费| 久久久无码精品亚洲日韩蜜臀浪潮| 精品国产综合区久久久久久| 久久99国产精品久久99| 无码精品久久久天天影视| 久久精品卫校国产小美女| 久久国产AVJUST麻豆| 人妻无码精品久久亚瑟影视| 中文字幕一区二区三区久久网站| 国产精品美女久久久m| 久久亚洲AV成人无码电影| 久久久久女人精品毛片| 久久偷看各类wc女厕嘘嘘| 亚洲日韩中文无码久久| 久久w5ww成w人免费| 国产一区二区三区久久| 久久se精品一区精品二区| 久久国产精品国产自线拍免费| 国产精品99久久不卡|