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

            AV无码久久久久不卡蜜桃| 久久久久久青草大香综合精品| 一级a性色生活片久久无少妇一级婬片免费放| 久久精品成人欧美大片| 欧美亚洲国产精品久久| 久久综合九色综合精品| 久久天天躁狠狠躁夜夜2020一| 久久综合丝袜日本网| 久久久久亚洲国产| 久久艹国产| 人妻无码久久一区二区三区免费| 99久久精品九九亚洲精品| 亚洲AV无一区二区三区久久 | 日韩av无码久久精品免费| 国产99久久久国产精品~~牛| 亚洲欧美日韩久久精品第一区| 久久本道久久综合伊人| 精品国产乱码久久久久久郑州公司 | 久久人人爽人人爽人人片AV高清| 99久久中文字幕| 日韩人妻无码精品久久久不卡| 老司机午夜网站国内精品久久久久久久久 | 久久精品国产亚洲av水果派| 日韩影院久久| 91久久精品国产91性色也| 国内高清久久久久久| 色天使久久综合网天天| 久久影院午夜理论片无码| 国产精品久久久天天影视香蕉| 狠狠色丁香婷婷久久综合不卡| 99久久久精品免费观看国产| 中文字幕日本人妻久久久免费| 国产精品久久久久久久久久影院| 四虎影视久久久免费| 一本久久免费视频| 伊人色综合久久天天人守人婷 | 看久久久久久a级毛片| 亚洲精品无码久久久久去q| 国产A三级久久精品| 久久丫精品国产亚洲av| 国产美女久久精品香蕉69|