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

            QuXiao

            每天進(jìn)步一點(diǎn)點(diǎn)!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評(píng)論 :: 0 Trackbacks

            PKU 1639 Picnic Planning解題報(bào)告

             

            分類:

            圖論、最小度限制生成樹

             

            原題:

            Picnic Planning

            Time Limit: 5000MS

            Memory Limit: 10000K

            Description

            The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone's cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother's house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother's car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.

            Input

            Input will consist of one problem instance. The first line will contain a single integer n indicating the number of highway connections between brothers or between brothers and the park. The next n lines will contain one connection per line, of the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park and a brother's name (in either order), and dist is the integer distance between them. These roads will all be 2-way roads, and dist will always be positive.The maximum number of brothers will be 20 and the maximumlength of any name will be 10 characters.Following these n lines will be one final line containing an integer s which specifies the number of cars which can fit in the parking lot of the picnic site. You may assume that there is a path from every brother's house to the park and that a solution exists for each problem instance.

            Output

            Output should consist of one line of the form
            Total miles driven: xxx
            where xxx is the total number of miles driven by all the brothers' cars.

            Sample Input

            10

            Alphonzo Bernardo 32

            Alphonzo Park 57

            Alphonzo Eduardo 43

            Bernardo Park 19

            Bernardo Clemenzi 82

            Clemenzi Park 65

            Clemenzi Herb 90

            Clemenzi Eduardo 109

            Park Herb 24

            Herb Eduardo 79

            3

            Sample Output

            Total miles driven: 183

             

             

            題目大意:

            一些人想從各自的家中開車到一個(gè)地方野餐,每個(gè)人的家中都可以容納無限多的車子,每個(gè)人的車子可以容納無限多的人。每個(gè)人可以先開車到另一人家中,將車停在那人家中,兩人(或多人)再開同一輛車開往目的地。但野餐的地方只有有限個(gè)停車位k,告訴你一些路程的長度,問你將所有人都聚集再野餐地點(diǎn),所使用的最短路程是多少。

             

            思路:

            因?yàn)轭}目中說到,一個(gè)人可以先開車到其他人家中,然后他們?cè)僖黄痖_車前往目的地,所以將問題抽象出來,將各人的家和目的地看作點(diǎn),將各個(gè)路程看作邊,若沒有目的地停車位(點(diǎn)的度)的限制,問題就可以轉(zhuǎn)化為求最小生成樹的問題。但加上了對(duì)某一點(diǎn)度的限制,問題就變得復(fù)雜了。

            假設(shè),若我們將度限制條件放在一邊,直接求最小生成樹。如果在最小生成樹中,目的地所在點(diǎn)的度數(shù)已經(jīng)滿足degree <= k,那么度限制生成樹就已經(jīng)得到了。因?yàn)椴豢赡苡斜人鼨?quán)值和更小的生成樹了,并且點(diǎn)的度數(shù)滿足條件。

            還有一種情況,那就是先按最小生成樹算法得到的生成樹中,目的地所在點(diǎn)的度數(shù)degree > k,那么很自然的,我們就要想到刪去degree-k條樹中與規(guī)定點(diǎn)相連的邊,使得它滿足度限制要求。每刪去邊之后,都要再加上一條邊,否則圖就會(huì)不連通,但是,又應(yīng)該怎樣刪邊呢?假設(shè),規(guī)定點(diǎn)的度數(shù)為t,那么就有t根與規(guī)定點(diǎn)相連的子樹T1T2、……、Tt,若刪去Ti與規(guī)定點(diǎn)相連的那條邊,Ti這棵子樹就“懸空”了,必須將Ti這棵樹“架”到其他子樹上才可以。經(jīng)過這樣一次的“刪添”操作之后,修改之后的圖仍然是棵樹,但規(guī)定點(diǎn)的度數(shù)減少了1,只要這樣進(jìn)行t-k次,就可以得到滿足條件的度限制生成樹了。但怎樣保證最小呢?只要在每次的“刪添”操作時(shí),保證“添”的邊的權(quán)值減去“刪”的邊的權(quán)值的差值(必大于等于0)最小就可以了。

            除了這種方法,lrj的書上還介紹了另一種方法。其大致思想是:現(xiàn)將規(guī)定點(diǎn)以及與它相連的邊都去掉,再在剩下的圖中求出每個(gè)連通分量的最小生成樹,在進(jìn)行“差額最小添刪操作”,求出滿足度限制的情況下的可能的權(quán)值,在其中不斷更新樹的權(quán)值和。具體算法將黑書P300~P303

             

             

            代碼:

             

            #include <iostream>

            #include <map>

            #include <string>

            #include <vector>

            #include <algorithm>

            using namespace std;

             

            const int MAX = 50;

             

            struct Edge

            {

                     int a, b;

                     int len;

            };

             

            vector<Edge> edge;

            map<string, int> nameIndex;

            int G[MAX][MAX];

            int tree[MAX][MAX];

            int n, m, k;

            int parkIndex;

            int degree[MAX];

            int treeDegree[MAX];

            int p[MAX];

            int inTree[MAX];

            int rank[MAX];

            int minCost;

            int treeTag[MAX];             //對(duì)子樹進(jìn)行標(biāo)記

            int visited[MAX];

            int subTreeNum;

             

            bool operator< (Edge e1, Edge e2)

            {

                     return ( e1.len < e2.len );

            }

             

             

            void Input ()

            {

                     string a, b;

                     int index1, index2;

                     int len;

                     Edge e;

                     n = 0;

                     cin>>m;

                     for (int i=0; i<m; i++)

                     {

                               cin>>a>>b>>len;

                               if ( nameIndex.find(a) == nameIndex.end() )

                               {

                                        nameIndex[a] = n;

                                        index1 = n;

                                        n ++;

                               }

                               else

                               {

                                        index1 = nameIndex[a];

                               }

             

                               if ( nameIndex.find(b) == nameIndex.end() )

                               {

                                        nameIndex[b] = n;

                                        index2 = n;

                                        n ++;

                               }

                               else

                               {

                                        index2 = nameIndex[b];

                               }

             

                               if ( a == "Park" )

                                        parkIndex = index1;

                               if ( b == "Park" )

                                        parkIndex = index2;

                               G[index1][index2] = G[index2][index1] = len;

                               e.a = index1;

                               e.b = index2;

                               e.len = len;

                               edge.push_back(e);

                               degree[index1] ++;

                               degree[index2] ++;

                     }

             

                     cin>>k;

            }

             

            int Find (int x)

            {

                int t, root, w;

                t = x;

                while ( p[t] != -1 )

                               t = p[t];

                root = t;

                t = x;

                while ( p[t] != -1 )

                {

                               w = p[t];

                               p[t] = root;

                               t = w;

                }

                    

                return root;

            }

             

            void Union (int x, int y)

            {

                     int r1, r2;

                     r1 = Find(x);

                     r2 = Find(y);

                    

                     if ( rank[r1] >= rank[r2] )

                     {

                               p[r2] = r1;

                               if ( rank[r1] == rank[r2] )

                                        rank[r1]++;

                     }

                     else

                               p[r1] = r2;

            }

             

             

            bool Kruskal ()

            {

                     int i, r1, r2, k, total, Max;

                     memset(p, -1, sizeof(p));

                     memset(inTree, 0, sizeof(inTree));

                     memset(rank, 1, sizeof(rank));

                     //qsort(edge, edgeNum, sizeof(edge[0]), cmp);

                     sort(edge.begin(), edge.end());

             

                Max = -1;

                     k = 0;

                     minCost = 0;

                     for (i=0; i<edge.size() && k<n-1; i++)

                     {

             

                               r1 = Find(edge[i].a);

                               r2 = Find(edge[i].b);

                               if ( r1 != r2 )

                               {

                                        tree[edge[i].a][edge[i].b] = tree[edge[i].b][edge[i].a] = edge[i].len;

                                        //cout<<edge[i].a<<' '<<edge[i].b<<endl;

                                        Union(r1, r2);

                                        inTree[i] = 1;

                                        treeDegree[edge[i].a] ++;

                                        treeDegree[edge[i].b] ++;

                                        k++;

                                        minCost += edge[i].len;

                               }

                     }

             

             

                     if ( k == n - 1 )

                    return true;

                     else

                               return false;

            }

             

             

            void DFS (int cur, int index)

            {

                     visited[cur] = 1;

                     treeTag[cur] = index;

                     int i;

                     for (i=0; i<n; i++)

                     {

                               if ( tree[cur][i] && !visited[i] )

                               {

                                        DFS (i, index);

                               }

                     }

            }

             

            void MakeTreeTag ()

            {

                     int i;

                     subTreeNum = 0;

                     memset(visited, 0, sizeof(visited));

                     visited[parkIndex] = 1;

                     memset(treeTag, -1, sizeof(treeTag));

                     for (i=0; i<n; i++)

                     {

                               if ( tree[parkIndex][i] )

                                        DFS (i, subTreeNum++);

                     }

            }

             

            //將原來的子樹架在另一棵樹上

            void ChangeTreeTag (int pre, int cur)

            {

                     int i;

                     for (i=0; i<n; i++)

                               if ( treeTag[i] == pre )

                                        treeTag[i] = cur;

            }

             

            //從當(dāng)前子樹查找與其他子樹相連的最小邊

            Edge FindMinEdge (int curTag)

            {

                     int i;

                     Edge e;

                     e.len = -1;

                     for (i=0; i<edge.size(); i++)

                     {

                               if ( ((treeTag[edge[i].a] == curTag && treeTag[edge[i].b] != curTag && edge[i].b != parkIndex)

                                        || (treeTag[edge[i].b] == curTag && treeTag[edge[i].a] != curTag && edge[i].a != parkIndex) )

                                        && G[edge[i].a][edge[i].b] )

                               {

                                        if ( e.len == -1 || edge[i].len < e.len )

                                        {

                                                 e.a = edge[i].a;

                                                 e.b = edge[i].b;

                                                 e.len = edge[i].len;

                                        }

                               }

                     }

                     return e;

            }

             

             

            void DeleteAdd ()

            {

                     int i, minDif, delTag, newTag;

                     minDif = -1;

                     Edge addEdge, delEdge, temp;

                     for (i=0; i<n; i++)

                     {

                               if ( i == parkIndex )

                                        continue;

                               temp = FindMinEdge(treeTag[i]);

                               if ( temp.len == -1 )

                                        continue;

                               if ( tree[parkIndex][i] && ( minDif == -1 || temp.len - tree[parkIndex][i] < minDif) )

                               {

                                        minDif = temp.len - tree[parkIndex][i];

                                        addEdge = temp;

                                        delEdge.a = parkIndex;

                                        delEdge.b = i;

                                        delTag = treeTag[i];

                                        if ( treeTag[addEdge.a] != delTag )

                                                 newTag = treeTag[addEdge.a];

                                        else

                                                 newTag = treeTag[addEdge.b];

                               }

                     }

             

                     tree[delEdge.a][delEdge.b] = tree[delEdge.b][delEdge.a] = 0;

                     G[delEdge.a][delEdge.b] = G[delEdge.b][delEdge.a] = 0;

                     tree[addEdge.a][addEdge.b] = tree[addEdge.b][addEdge.a] = addEdge.len;

                    

                     minCost += minDif;

             

                     ChangeTreeTag(delTag, newTag);

            }

             

             

            void Solve ()

            {

                     Kruskal();

                     if ( treeDegree[parkIndex] <= k )

                     {

                               cout<<"Total miles driven: "<<minCost<<endl;

                               return;

                     }

             

                     MakeTreeTag ();

             

                     int i;

                     for (i=0; i<treeDegree[parkIndex]-k; i++)

                               DeleteAdd();

             

                     cout<<"Total miles driven: "<<minCost<<endl;

            }

             

            int main ()

            {

                     Input ();

                     Solve ();

             

                     return 0;

            }

            posted on 2008-07-30 19:10 quxiao 閱讀(950) 評(píng)論(1)  編輯 收藏 引用 所屬分類: ACM

            評(píng)論

            # re: PKU 1639 Picnic Planning 2011-03-28 19:28 Chengsir
            如果單單從算法來考慮,要求求的是根的出度剛好為 k的最小生成樹,那應(yīng)該怎么求呀/.  回復(fù)  更多評(píng)論
              

            久久精品人人做人人爽电影蜜月| 久久久久国产一级毛片高清版| 久久精品成人欧美大片| 久久久精品久久久久特色影视| 久久综合狠狠综合久久97色| 18岁日韩内射颜射午夜久久成人 | 久久国产高潮流白浆免费观看| 青青热久久综合网伊人| 久久乐国产综合亚洲精品| 国产精品女同久久久久电影院| 久久91这里精品国产2020| 浪潮AV色综合久久天堂| 日韩va亚洲va欧美va久久| 久久久无码精品亚洲日韩按摩| 久久久久亚洲AV成人网| 精品久久久久久无码专区| 久久久久久久免费视频| 成人精品一区二区久久| 久久无码人妻一区二区三区午夜| 九九久久精品无码专区| 国产精品久久久天天影视香蕉| 青春久久| 国产精品成人无码久久久久久| 久久精品人人槡人妻人人玩AV| 亚洲国产综合久久天堂 | 久久青青草原国产精品免费 | 无码任你躁久久久久久久| 精品久久久久久无码专区| 国产69精品久久久久9999APGF| 久久久精品日本一区二区三区| 国产精品嫩草影院久久| 2021久久国自产拍精品| 无码日韩人妻精品久久蜜桃| 久久丫忘忧草产品| 久久青青色综合| A级毛片无码久久精品免费| 合区精品久久久中文字幕一区| 久久一区二区三区免费| 亚洲伊人久久成综合人影院 | 99精品久久精品一区二区| 久久精品中文无码资源站|