• <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, 評(píng)論 - 47, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 2135 Farm Tour 最小費(fèi)用最大流

            第一次寫這玩意,還真有點(diǎn)麻煩,出了點(diǎn)問題。然后看了一下別人的代碼,
            發(fā)現(xiàn)雙向邊,要分成兩個(gè)單向邊來插入。長見識(shí)了。
            而且費(fèi)用的值有正有負(fù),最好用SPFA來找最短路徑。

            思路:
            建立一個(gè)超級(jí)源點(diǎn),跟點(diǎn)1連起來,容量為2。
            建立一個(gè)超級(jí)匯點(diǎn),跟點(diǎn)N連起來,容量為2。
            其他的邊容量均為1。

            #include <stdio.h>
            #include 
            <stdlib.h>
            #include 
            <string.h>

            #define MAX_COST (1 << 30)
            #define MAX_E (20032 * 4)
            #define MAX_V 2048
            #define MAX_CAP 2
            #define dbp printf

            struct edge_node {
                
            int idx, flow, cap, cost;
                
            struct edge_node *next;
            }
            ;

            struct graph_node {
                
            struct edge_node edges[MAX_E], *map[MAX_V], *path_edge[MAX_V];
                
            int edges_cnt, vertexs_cnt, path_idx[MAX_V];
                
            int min_dis[MAX_V];
            }
            ;

            inline 
            int min(int a, int b)
            {
                
            return a < b ? a : b;
            }


            inline 
            void graph_init(struct graph_node *g, int vertexs_cnt)
            {
                g
            ->vertexs_cnt = vertexs_cnt;
                g
            ->edges_cnt = 0;
                memset(g
            ->map, 0, vertexs_cnt * sizeof(g->map[0]));
            }


            inline 
            void graph_dump(struct graph_node *g)
            {
                
            struct edge_node *e;
                
            int i;

                
            for (i = 0; i < g->vertexs_cnt; i++{
                    dbp(
            "#%d: ", i);
                    
            for (e = g->map[i]; e; e = e->next) 
                        dbp(
            "%dc%d ", e->idx, e->cost);
                    dbp(
            "\n");
                }

            }


            inline 
            void graph_addedge(struct graph_node *g, 
                                      
            int from, int to, 
                                      
            int cost, int cap = 0
                                      )
            {
                
            struct edge_node *e;

                
            if (g->edges_cnt >= _countof(g->edges)) {
                    printf(
            "too many edges\n");
                    
            return ;
                }


                e 
            = &g->edges[g->edges_cnt++];
                e
            ->idx = to;
                e
            ->cost = cost;
                e
            ->cap = cap;
                e
            ->next = g->map[from];
                g
            ->map[from] = e;
            }


            inline 
            int __conn_default(struct edge_node *e)
            {
                
            return 1;
            }


            inline 
            void graph_spfa(struct graph_node *g, int idx, 
                                   
            int (*conn)(struct edge_node *= __conn_default
                                   )
            {
                
            static int queue[MAX_V], vis[MAX_V], tm, head, tail;
                
            int i, val;
                
            struct edge_node *e;

                
            for (i = 0; i < g->vertexs_cnt; i++)
                    g
            ->min_dis[i] = MAX_COST;
                g
            ->min_dis[idx] = 0;
                
                head 
            = tail = 0;
                tm
            ++;
                queue[tail
            ++= idx;

                
            while (head != tail) {
                    idx 
            = queue[head++];
                    vis[idx] 
            = 0;
                    
            for (e = g->map[idx]; e; e = e->next) {
                        
            if (!conn(e))
                            
            continue;
                        val 
            = g->min_dis[idx] + e->cost;
                        
            if (val >= g->min_dis[e->idx])
                            
            continue;
                        g
            ->path_idx[e->idx] = idx;
                        g
            ->path_edge[e->idx] = e;
                        g
            ->min_dis[e->idx] = val;
                        
            if (vis[e->idx] == tm) 
                            
            continue;
                        queue[tail
            ++= e->idx;
                        vis[e
            ->idx] = tm;
                    }

                }

            }


            inline 
            int __conn_mfmc(struct edge_node *e)
            {
                
            return e->cap - e->flow > 0;
            }


            inline 
            void graph_mfmc(struct graph_node *g, int s, int t, int *flow, int *cost)
            {
                
            int i, j, min_c;
                
            struct edge_node *e;

                
            for (i = 0; i < g->edges_cnt; i++)
                    g
            ->edges[i].flow = 0;

                
            *flow = 0;
                
            *cost = 0;
                
            while (1{
                    graph_spfa(g, s, __conn_mfmc);
                    
            if (g->min_dis[t] == MAX_COST)
                        
            break ;
                    min_c 
            = MAX_CAP;
                    
            for (i = t; i != s; i = g->path_idx[i]) {
                        e 
            = g->path_edge[i];
                        min_c 
            = min(min_c, e->cap - e->flow);
                    }

                    
            for (i = t; i != s; i = g->path_idx[i]) {
                        j 
            = g->path_edge[i] - g->edges;
                        
            *cost += g->edges[j].cost * min_c;
                        g
            ->edges[j].flow += min_c;
                        g
            ->edges[j ^ 1].flow -= min_c;
                    }

                    
            *flow += min_c;
                }

            }


            int main()
            {
                
            int N, M, from, to, cost, flow;
                
            static struct graph_node g;

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

                scanf(
            "%d%d"&N, &M);
                graph_init(
            &g, N + 2);
                
            while (M--{
                    scanf(
            "%d%d%d"&from, &to, &cost);
                    graph_addedge(
            &g, from, to, cost, 1);
                    graph_addedge(
            &g, to, from, -cost, 0);
                    graph_addedge(
            &g, to, from, cost, 1);
                    graph_addedge(
            &g, from, to, -cost, 0);
                }

                graph_addedge(
            &g, 0102);
                graph_addedge(
            &g, 1000);
                graph_addedge(
            &g, N, N + 102);
                graph_addedge(
            &g, N + 1, N, 00);
                graph_mfmc(
            &g, 0, N + 1&flow, &cost);
                printf(
            "%d\n", cost);

                
            return 0;
            }

            posted on 2010-04-06 23:40 糯米 閱讀(799) 評(píng)論(4)  編輯 收藏 引用 所屬分類: POJ

            評(píng)論

            # re: POJ 2135 Farm Tour 最小費(fèi)用最大流  回復(fù)  更多評(píng)論   

            "發(fā)現(xiàn)雙向邊,要分成兩個(gè)單向邊來插入。"
            請問一下為什么要建雙向邊呢?
            2010-09-02 00:18 | siurz

            # re: POJ 2135 Farm Tour 最小費(fèi)用最大流  回復(fù)  更多評(píng)論   

            @siurz
            同樣期待
            2011-02-06 16:43 | .。

            # re: POJ 2135 Farm Tour 最小費(fèi)用最大流  回復(fù)  更多評(píng)論   

            @.。
            想明白了,因?yàn)楫?dāng)a->b的邊走了之后,b->a有兩條邊,其中一條的費(fèi)用為正,一條的費(fèi)用為負(fù)。顯然會(huì)選擇為負(fù)的,而為負(fù)的正是剛剛其走過的a->b的反向邊,這樣就相當(dāng)于剛剛的a->b沒有走。
            2011-02-06 16:58 | .。

            # re: POJ 2135 Farm Tour 最小費(fèi)用最大流  回復(fù)  更多評(píng)論   

            如火熱
            2011-08-17 16:24 |
            久久婷婷五月综合色高清| 日产精品久久久久久久性色| 久久国产精品成人免费| 久久亚洲私人国产精品vA | 亚洲精品NV久久久久久久久久| 欧美亚洲另类久久综合婷婷| 久久久无码精品亚洲日韩京东传媒 | 久久婷婷五月综合成人D啪| 久久天天躁狠狠躁夜夜avapp| 91精品国产综合久久香蕉 | 九九99精品久久久久久| 日本国产精品久久| 国产成人精品久久二区二区| 亚洲精品国精品久久99热| 久久久噜噜噜www成人网| 99久久精品国产一区二区蜜芽| 无码国内精品久久综合88 | 狠狠精品干练久久久无码中文字幕| 国产免费久久精品99re丫y| 国产精品狼人久久久久影院| 欧美黑人又粗又大久久久| 久久精品国产福利国产琪琪| a高清免费毛片久久| 亚洲国产精品一区二区久久hs| 久久精品国产亚洲av瑜伽| 久久精品视频网| 久久se精品一区精品二区| 久久亚洲日韩精品一区二区三区 | 久久伊人影视| 欧美性大战久久久久久| 国产精品久久久久一区二区三区| 精品久久久久久国产潘金莲| 91精品国产91久久综合| 久久青青草原精品国产| 久久人人爽人人爽人人AV| 狠狠色婷婷久久综合频道日韩| 国产精品久久久香蕉| 日本五月天婷久久网站| 中文字幕人妻色偷偷久久| 国产精品99久久久精品无码| 香蕉久久av一区二区三区|