• <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
            數據加載中……

            POJ 1984 Navigation Nightmare 并查集

            思路:
            每次新增點a -> b的時候,union (b, a),節點中保存的是距離的偏移量。
            查詢a, b的關系的時候,如果a, b不是一類,就輸出-1,如果是的話,就將a,b的偏移量相加然后輸出。

            #include <stdio.h>

            struct node {
                
            int a, b;
                
            struct node *next;
            }
            ;

            struct node nodes[10032];

            struct {
                
            int from, to, len;
                
            char dir;
                
            struct node *query;
            }
             arr[40032];

            struct {
                
            int parent, x, y;
            }
             set[400032];

            int N, M;

            __inline 
            int abs(int i)
            {
                
            return i > 0 ? i : -i;
            }


            int set_find(int i)
            {
                
            int r, p;

                p 
            = set[i].parent;
                
            if (!p)
                    
            return i;
                r 
            = set_find(p);
                
            set[i].x += set[p].x;
                
            set[i].y += set[p].y;
                
            set[i].parent = r;
                
            return r;
            }


            void set_union(int from, int to, int x, int y)
            {
                
            int r = set_find(to);
                
            set[r].parent = from;
                
            set[r].x = x - set[to].x;
                
            set[r].y = y - set[to].y;
            }


            int main()
            {
                
            int i, j, k, ia, ib, x, y;
                
            char str[16];
                
            struct node *t, **pt;

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

                scanf(
            "%d%d"&N, &M);
                
            for (i = 1; i <= M; i++{
                    scanf(
            "%d%d%d%s"&arr[i].from, &arr[i].to, &arr[i].len, str);
                    arr[i].dir 
            = str[0];
                }

                scanf(
            "%d"&k);
                
            for (i = 0; i < k; i++{
                    scanf(
            "%d%d%d"&nodes[i].a, &nodes[i].b, &j);
                    
            for (pt = &arr[j].query; *pt; pt = &(*pt)->next);
                    
            *pt = &nodes[i];
                }

                
            for (i = 1; i <= M; i++{
                    
            switch (arr[i].dir) {
                    
            case 'E': x = arr[i].len; y = 0break;
                    
            case 'W': x = -arr[i].len; y = 0break;
                    
            case 'N': x = 0; y = arr[i].len; break;
                    
            case 'S': x = 0; y = -arr[i].len; break;
                    }

                    set_union(arr[i].from, arr[i].to, x, y);
                    
            for (t = arr[i].query; t; t = t->next) {
                        ia 
            = set_find(t->a);
                        ib 
            = set_find(t->b);
                        
            if (ia != ib)
                            j 
            = -1;
                        
            else
                            j 
            = abs(set[t->a].x - set[t->b].x) + abs(set[t->a].y - set[t->b].y);
                        printf(
            "%d\n", j);
                    }

                }


                
            return 0;
            }


            posted on 2010-03-09 18:08 糯米 閱讀(370) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            欧美国产成人久久精品| 精品无码久久久久久久久久| 久久成人18免费网站| 久久91精品国产91久久小草| 青青草原精品99久久精品66| 99精品久久精品一区二区| 久久婷婷色香五月综合激情| 国产香蕉久久精品综合网| 伊人久久大香线蕉AV一区二区| 欧美与黑人午夜性猛交久久久| 少妇久久久久久被弄到高潮| 久久九九免费高清视频| 亚洲精品国产自在久久| 欧美激情一区二区久久久| 久久久久亚洲AV无码麻豆| 99精品国产在热久久无毒不卡| 精品久久久久久中文字幕| 国产精品无码久久四虎| 国内精品久久久久影院老司| 人妻无码中文久久久久专区| 久久美女网站免费| 久久夜色撩人精品国产| 亚洲国产精品久久久天堂| 国产 亚洲 欧美 另类 久久| 亚洲欧美国产日韩综合久久 | 国产精品一久久香蕉产线看| 国产一区二区精品久久| 亚洲国产成人精品女人久久久| 中文无码久久精品| 国内精品伊人久久久久影院对白| 久久综合亚洲色一区二区三区| 精品久久久久久中文字幕人妻最新| 亚洲国产天堂久久综合网站| 久久www免费人成看片| 久久亚洲综合色一区二区三区| 精产国品久久一二三产区区别| 久久亚洲国产精品一区二区| 久久精品国产亚洲AV香蕉| 久久精品无码一区二区三区日韩| 色综合久久中文字幕无码| 色欲综合久久躁天天躁|