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

            综合久久精品色| 少妇久久久久久被弄到高潮 | 伊人色综合久久天天人守人婷 | 77777亚洲午夜久久多喷| WWW婷婷AV久久久影片| 精品无码人妻久久久久久| 久久久久久精品成人免费图片| 国产精品美女久久久| 四虎影视久久久免费| 韩国无遮挡三级久久| 亚洲va久久久噜噜噜久久 | 欧美一级久久久久久久大| 久久人人爽人人爽人人AV东京热| 狠狠色伊人久久精品综合网 | 久久久久中文字幕| 区久久AAA片69亚洲| 国产精品亚洲美女久久久| 久久AV高潮AV无码AV| 久久99精品久久久久久不卡| 久久香蕉超碰97国产精品| 亚洲国产精品嫩草影院久久| 国内精品久久久久国产盗摄| 1000部精品久久久久久久久| 狠狠精品久久久无码中文字幕| 国产精品日韩深夜福利久久| 国产精品视频久久久| 日韩人妻无码一区二区三区久久 | 久久99久久无码毛片一区二区| 久久精品国产亚洲av麻豆色欲 | 久久国产欧美日韩精品| A级毛片无码久久精品免费| 色天使久久综合网天天| 久久精品中文无码资源站| 合区精品久久久中文字幕一区| 久久久久黑人强伦姧人妻| 狠狠色综合网站久久久久久久| 激情五月综合综合久久69| 精品久久久久一区二区三区| 久久精品国产99久久香蕉| 久久久精品久久久久特色影视| 一本色综合久久|