青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

QuXiao

每天進步一點點!

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks

PKU 1639 Picnic Planning解題報告

 

分類:

圖論、最小度限制生成樹

 

原題:

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

 

 

題目大意:

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

 

思路:

因為題目中說到,一個人可以先開車到其他人家中,然后他們再一起開車前往目的地,所以將問題抽象出來,將各人的家和目的地看作點,將各個路程看作邊,若沒有目的地停車位(點的度)的限制,問題就可以轉化為求最小生成樹的問題。但加上了對某一點度的限制,問題就變得復雜了。

假設,若我們將度限制條件放在一邊,直接求最小生成樹。如果在最小生成樹中,目的地所在點的度數已經滿足degree <= k,那么度限制生成樹就已經得到了。因為不可能有比它權值和更小的生成樹了,并且點的度數滿足條件。

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

除了這種方法,lrj的書上還介紹了另一種方法。其大致思想是:現將規定點以及與它相連的邊都去掉,再在剩下的圖中求出每個連通分量的最小生成樹,在進行“差額最小添刪操作”,求出滿足度限制的情況下的可能的權值,在其中不斷更新樹的權值和。具體算法將黑書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];             //對子樹進行標記

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;

}

 

//從當前子樹查找與其他子樹相連的最小邊

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 閱讀(970) 評論(1)  編輯 收藏 引用 所屬分類: ACM

評論

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            一区精品在线播放| 国产精品扒开腿做爽爽爽软件| 国产精品一区免费观看| 亚洲一区精品在线| 亚洲综合视频1区| 好看的亚洲午夜视频在线| 久久一区激情| 欧美激情视频在线播放| 一区二区欧美日韩| 亚洲免费视频一区二区| 韩国女主播一区二区三区| 欧美激情视频一区二区三区在线播放| 亚洲欧美日韩在线综合| 午夜在线视频观看日韩17c| 一区二区三区在线视频播放| 亚洲日本成人女熟在线观看| 欧美午夜免费影院| 久久婷婷av| 欧美日韩午夜在线视频| 久久精品视频在线看| 蘑菇福利视频一区播放| 亚洲欧美激情在线视频| 久久久亚洲精品一区二区三区| 99国产精品久久久久老师| 亚洲欧美激情四射在线日 | 午夜精品区一区二区三| 久久高清国产| 亚洲免费网址| 欧美freesex交免费视频| 亚洲女与黑人做爰| 欧美成人午夜激情在线| 久久久999精品免费| 欧美日韩国产电影| 毛片一区二区| 国产美女精品一区二区三区| 亚洲高清在线视频| 国产在线视频欧美| 亚洲视频一二| 日韩小视频在线观看| 欧美在线观看视频在线| 中日韩美女免费视频网站在线观看| 久久经典综合| 久久精品亚洲热| 欧美午夜久久久| 亚洲精品社区| 亚洲精品婷婷| 免费成人高清视频| 美女久久网站| 影音国产精品| 久久免费视频在线观看| 久久久999精品免费| 国产精品日韩欧美一区二区| 99精品欧美一区二区三区综合在线| 最新亚洲视频| 美腿丝袜亚洲色图| 欧美搞黄网站| 亚洲激情网站免费观看| 麻豆成人在线观看| 欧美国产日韩精品| 亚洲韩国青草视频| 欧美xxx成人| 亚洲欧洲综合另类| 99精品99久久久久久宅男| 欧美黑人一区二区三区| 亚洲日本欧美| 亚洲午夜av在线| 国产精品人人做人人爽| 亚洲欧美怡红院| 久久久在线视频| 精品9999| 欧美成人免费播放| 亚洲欧洲在线免费| 亚洲一区二区三区在线| 国产精品免费一区豆花| 午夜激情亚洲| 欧美**字幕| 一本大道av伊人久久综合| 欧美日韩国内| 亚洲欧美资源在线| 国产精品久久久| 亚洲一区欧美激情| 久久精品99国产精品酒店日本| 黄色成人av| 欧美国产一区二区在线观看| 亚洲毛片av| 久久国产福利国产秒拍| 1024成人网色www| 欧美日韩精品一区二区天天拍小说 | 性欧美xxxx视频在线观看| 国产亚洲欧美日韩在线一区| 久久一区国产| 一本色道久久88亚洲综合88| 久久免费观看视频| 9色精品在线| 国产一区二区三区在线观看视频 | 亚洲淫性视频| 好看的日韩视频| 欧美日韩一区在线视频| 欧美与欧洲交xxxx免费观看| 亚洲黄色影院| 老司机午夜精品视频| 一本大道久久a久久精品综合| 国产一区二区三区的电影| 欧美国产日韩一区| 欧美在线亚洲在线| 夜夜爽av福利精品导航| 欧美不卡一卡二卡免费版| 亚洲欧美日韩一区二区三区在线| 亚洲国产aⅴ天堂久久| 国产精品女主播| 欧美69wwwcom| 久久国产精品99国产| 99re视频这里只有精品| 欧美14一18处毛片| 久久国产精品黑丝| 亚洲一区在线播放| 亚洲精品国产精品国自产观看| 国产视频久久久久久久| 欧美日韩国产色视频| 久久久久久久综合| 亚洲综合导航| 一区二区三区四区五区精品视频 | 亚洲一区二区三区四区中文 | 亚洲视频在线免费观看| 伊人伊人伊人久久| 国产深夜精品| 国产日韩一区在线| 国产精品推荐精品| 欧美性开放视频| 欧美日韩日日骚| 欧美精品一区二区三区四区| 久热精品视频在线免费观看| 久久精品一区二区三区四区 | 欧美aⅴ99久久黑人专区| 久久精品二区亚洲w码| 欧美一区二区三区电影在线观看| 亚洲在线成人精品| 亚洲欧美日韩国产综合| 亚洲制服欧美中文字幕中文字幕| 中文国产成人精品久久一| 亚洲精品一区二区在线| 亚洲精品美女在线| 亚洲精品免费电影| 一卡二卡3卡四卡高清精品视频| 精品999久久久| 在线国产精品播放| 亚洲第一偷拍| 亚洲精品免费在线观看| 99精品久久久| 亚洲专区一区二区三区| 欧美亚洲一级片| 久久精品国产在热久久| 久久一二三国产| 亚洲第一在线| av成人免费| 午夜国产欧美理论在线播放| 久久久久久久国产| 欧美不卡在线视频| 欧美日韩国产色视频| 国产精品一二三四| 韩国精品一区二区三区| 亚洲国产另类久久精品| av不卡在线| 久久九九精品| 亚洲国产精品免费| 中日韩美女免费视频网站在线观看 | 亚洲精品日韩久久| 中文在线资源观看视频网站免费不卡| 亚洲自拍16p| 蜜臀av一级做a爰片久久| 亚洲国产成人一区| 亚洲曰本av电影| 欧美成人一区二区三区在线观看| 欧美日韩中文字幕| 娇妻被交换粗又大又硬视频欧美| 日韩午夜激情电影| 久久精品视频99| 亚洲精品中文字| 久久精品亚洲一区二区| 欧美日韩高清在线一区| 国产综合18久久久久久| 一本久久a久久免费精品不卡| 久久久www成人免费毛片麻豆| 亚洲激情社区| 久久精品免费看| 国产精品一区2区| 亚洲伦伦在线| 六月丁香综合| 亚洲欧美日韩一区二区在线 | 亚洲一区www| 欧美大片网址| 伊人成年综合电影网| 亚洲综合二区| 亚洲精品欧美| 久久精品国产亚洲一区二区三区 | 久久亚洲电影| 国产一区二区精品久久91| 亚洲图片欧美日产| 亚洲区国产区| 欧美成人国产va精品日本一级|