• <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 2843 Cutting Cake 并查集

            思路:

            這題目非常牛逼!是道月賽的題目!看完題目我就放棄了。。直接看解題報告。
            解法果然牛逼!

            解題報告鏈接在此:
            http://acm.pku.edu.cn/JudgeOnline/images/contestreport/200606/G.htm

            代碼是照著解題報告寫的,不過還是很爛,好像3000+ms,實在佩服那些1000ms內的神牛們!

            #include <stdio.h>

            #define MAX_N 1024

            struct queue_node {
                
            int y, x;
            }
            ;

            int set[MAX_N][MAX_N], cut[MAX_N][MAX_N];
            int N, M;
            int left, top, right, bottom;

            struct queue_node queue[MAX_N * MAX_N];
            int head, tail;

            inline 
            int find(int *arr, int idx)
            {
                
            static int stk[MAX_N * MAX_N], sp;

                
            for (sp = 0; arr[idx]; idx = arr[idx])
                    stk[sp
            ++= idx;
                
            for (sp--; sp >= 0; sp--)
                    arr[stk[sp]] 
            = idx;

                
            return idx;
            }


            inline 
            void push(int y, int x)
            {
                
            if (x < left || x > right || y < top || y > bottom)
                    
            return ;
                
            if (cut[y][x])
                    
            return ;
                
                cut[y][x] 
            = 1;
                
            if (cut[y][x - 1&& cut[y][x + 1]) {
                    
            set[y][x] = x + 1;
                    
            set[y][x - 1= x + 1;
                }
             else if (cut[y][x - 1]) 
                    
            set[y][x - 1= x;
                
            else if (cut[y][x + 1])
                    
            set[y][x] = x + 1;
                
                queue[tail].y 
            = y;
                queue[tail].x 
            = x;
                tail
            ++;
            }


            inline 
            int bfs(int y, int x)
            {
                x 
            = find(set[y], x);
                
            if (cut[y][x])
                    x
            ++;
                
            if (x > right)
                    
            return 0;

                head 
            = tail = 0;
                push(y, x);
                
            while (head != tail) {
                    y 
            = queue[head].y;
                    x 
            = queue[head].x;
                    head
            ++;
                    push(y 
            - 1, x);
                    push(y 
            + 1, x);
                    push(y, x 
            - 1);
                    push(y, x 
            + 1);
                }


                
            return 1;
            }


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

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

                scanf(
            "%d%d"&N, &M);
                
            while (M--{
                    scanf(
            "%d%d%d%d"&left, &top, &right, &bottom);
                    ans 
            = 0;
                    
            for (i = top; i <= bottom; i++)
                        
            while (bfs(i, left))
                            ans
            ++;
                    printf(
            "%d\n", ans);
                }


                
            return 0;
            }

            posted on 2010-04-06 22:40 糯米 閱讀(319) 評論(1)  編輯 收藏 引用 所屬分類: POJ

            評論

            # re: POJ 2843 Cutting Cake 并查集  回復  更多評論   

            請問你上面e:\test\in.txt里面是什么內容,我也在想這個問題,但是沒弄明白,想用你代碼運行一下,謝謝了 我郵箱:236602203@qq.com
            2010-04-10 00:46 | 卡卡
            久久久久亚洲精品中文字幕| 热re99久久6国产精品免费| 国产精品久久久久无码av| 久久伊人精品青青草原高清| 国产福利电影一区二区三区久久老子无码午夜伦不 | 日日狠狠久久偷偷色综合96蜜桃| 久久精品国产亚洲7777| 亚洲精品乱码久久久久久蜜桃不卡| 久久这里只有精品18| 国产精品99久久不卡| 久久夜色精品国产噜噜亚洲AV| 亚洲国产精品久久久久久| 国产成人久久精品一区二区三区 | 国产成人精品免费久久久久| 久久久久久国产精品无码下载| 亚洲色欲久久久综合网东京热| 国产精品欧美久久久久无广告| 五月丁香综合激情六月久久| 久久久久国产一区二区| 91精品国产91久久综合| 久久精品国产99久久久古代| 久久99精品久久久久久噜噜| 久久精品九九亚洲精品| 久久精品国产清自在天天线| 四虎影视久久久免费观看| 大蕉久久伊人中文字幕| 欧美亚洲另类久久综合| 国产69精品久久久久777| 久久人人爽人人爽人人片AV不| 久久久久亚洲av成人网人人软件| 久久精品无码一区二区app| 66精品综合久久久久久久| 色综合色天天久久婷婷基地| 日本免费久久久久久久网站| 天天综合久久久网| 91超碰碰碰碰久久久久久综合| 超级碰久久免费公开视频| 91秦先生久久久久久久| 国内精品久久久久久中文字幕| 91麻精品国产91久久久久| 久久国产成人午夜aⅴ影院|