• <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 3169 Layout 差分約束

            思路:

            差分約束是個很神奇的東西,能將下面這種類型的不等式約束問題:
            d[1] - d[2] <= a
            d[4] - d[7] <= b
            ...
            求 d[x] 的最大/小值
            轉化為最短路徑的問題,真嗎的太牛逼了。
            原理呢,就是一個圖求出單源最短路徑之后。
            兩點之間的關系必然是滿足 d[u] + w[u,v] >= d[v] 的,沒法再松弛了。

            對于這道題,有兩種約束:
            1. 輸入里指明的約束
            2. d[1] <= d[2] <= d[3] .... <= d[N]

            建立完這兩種約束之后,然后spfa求一下最短路徑。
            如果有負環,就輸出 -1
            如果不連通,就輸出 -2

            #include <stdio.h>

            #define MAX_DIS 1000000032
            #define MAX_N 1024
            #define MAX_EDGES 65536

            struct edge_node {
                
            int i, w;
                
            struct edge_node *next;
            }
            ;

            int N, ML, MD;
            struct edge_node edges[MAX_EDGES], *map[MAX_N];
            int edges_cnt;
            int D[MAX_N], queue[MAX_N], head, tail, vis[MAX_N], tm, cnt[MAX_N];

            inline 
            void add_edge(int a, int b, int w)
            {
                
            struct edge_node *= &edges[edges_cnt++];

                e
            ->= b;
                e
            ->= w;
                e
            ->next = map[a];
                map[a] 
            = e;
            }


            inline 
            int push(int i, int d)
            {
                
            if (d >= D[i])
                    
            return 0;
                D[i] 
            = d;
                
            if (vis[i] == tm)
                    
            return 0;
                vis[i] 
            = tm;
                cnt[i]
            ++;
                
            if (cnt[i] >= N)
                    
            return 1;
                queue[tail
            ++= i;
                tail 
            &= MAX_N - 1;
                
            return 0;
            }


            inline 
            int spfa()
            {
                
            int i;
                
            struct edge_node *e;

                
            for (i = 1; i <= N; i++
                    D[i] 
            = MAX_DIS;
                tm
            ++;
                head 
            = tail = 0;
                push(
            10);
                
            while (head != tail) {
                    i 
            = queue[head++];
                    head 
            &= MAX_N - 1;
                    vis[i] 
            = 0;
                    
            for (e = map[i]; e; e = e->next) 
                        
            if (push(e->i, D[i] + e->w))
                            
            return 1;
                }


                
            return 0;
            }


            int main()
            {
                
            int a, b, w, i;

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

                scanf(
            "%d%d%d"&N, &ML, &MD);
                
            while (ML--{
                    scanf(
            "%d%d%d"&a, &b, &w);
                    add_edge(a, b, w);
                }

                
            while (MD--{
                    scanf(
            "%d%d%d"&a, &b, &w);
                    add_edge(b, a, 
            -w);
                }

                
            for (i = 2; i <= N; i++)
                    add_edge(i, i 
            - 10);

                
            if (spfa())
                    a 
            = -1;
                
            else
                    a 
            = (D[N] == MAX_DIS) ? -2 : D[N];
                printf(
            "%d\n", a);

                
            return 0;
            }

            posted on 2010-04-27 14:11 糯米 閱讀(455) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            久久天堂AV综合合色蜜桃网| 久久66热人妻偷产精品9| 久久99精品国产99久久6男男| 99精品久久精品一区二区| 久久久久久久综合日本亚洲 | 狠狠狠色丁香婷婷综合久久五月 | 狠狠88综合久久久久综合网| 一级做a爰片久久毛片人呢| 久久久久亚洲国产| 久久国产精品-久久精品| 久久久国产99久久国产一| 韩国无遮挡三级久久| 亚洲va久久久噜噜噜久久| 久久精品免费大片国产大片| 久久久亚洲欧洲日产国码aⅴ| 亚洲精品99久久久久中文字幕| 精品一区二区久久| 色欲久久久天天天综合网| 国产亚洲美女精品久久久| 久久本道伊人久久| 亚洲国产精品无码久久SM| 亚洲国产婷婷香蕉久久久久久| 久久精品一区二区| 久久久久久久97| 中文字幕久久波多野结衣av| 久久久久婷婷| 久久免费视频一区| 国产高潮国产高潮久久久91 | 一本综合久久国产二区| 色天使久久综合网天天| 日日狠狠久久偷偷色综合0| 久久96国产精品久久久| 91视频国产91久久久| 久久99免费视频| 91精品免费久久久久久久久| 久久久青草青青亚洲国产免观| 乱亲女H秽乱长久久久| 国产午夜精品久久久久免费视| 久久久久国产精品熟女影院 | 久久亚洲精品无码VA大香大香 | www.久久精品|