Coder Space

题意：给出若干个小矮人的家和一个公园，这些小矮人到公园去聚会，题中给了若干条路线，还有每条路线的长度，在这些路线上穿行需要开车，但是公园只可容纳一定数量的汽车，小矮人可以部分聚集到一起再一起开车到公园，求需要行驶的最短距离。 

思路：求最小生成树，其中某一个节点的度是限制的，即度限制最小生成树。 

解法：

(1)     由于公园的度是限制的，因此可以先忽略公园这个点，对其他的点求最小生成树，可能有多棵，即确切说应该是最小生成森林。

(2)     在每个连通分支中，选出到达公园最短的路，可知这些必定是最小限制生成树中的边，把这些边加到最小生成森林中，可得包括公园节点度为M的一棵最小生成树。

(3)     如果此时M>limit，则易知limit度限制树不存在。否则，公园节点的边从M增加到limit，每次做一次“差额最小添删操作”。即从公园节点V0添加一条到Vi的边，这样就形成一个环，然后删掉环里面最大的那条边（不与V0相连），差额为：cost(添加边) – cost(删除边)。枚举以V0为节点的未在生成树中的所有边，找出最小差额。如果差额大于0，即退出。否则，更新生成树权值：val = val + cost(添加边) – cost(删除边)。 

注意：对于找最长边，可以先用DFS遍历生成树，记录每个节点vi到V0点的最长边长，和最长边的端点，需要O(n)，然后每次以O(1)即可选出。进行一次添删边操作后，也需要O(n)时间维护。

源代码
  1#include<iostream>
  2#include<map>
  3#include<string>
  4#include<limits>
  5#include<queue>
  6
  7using namespace std;
  8
  9const int MAXN = 22;
 10const int INF = numeric_limits<int>::max();
 11
 12map<string,int> mTable;                                   //名字与编号映射表，Park编号为1
 13typedef map<string,int>::value_type valType;
 14
 15int G[MAXN][MAXN];                                        //路径图
 16bool MT[MAXN][MAXN];                                      //度限制最小生成树
 17
 18bool visited[MAXN];
 19int treeTag[MAXN];                                        //最小生成森林，树编号标记
 20int treeCnt;                                              //最小生成森林中树的棵数
 21
 22int maxEdge[MAXN][3];             //生成树中每个点到park点路径的最长边, 第二维中，0表示边长，1、2分别为最长边的两节点
 23
 24int Prim(int n,int s)             //求包括节点s的最小生成树，返回生成树的权值
 25{
 26    int lowcost[MAXN];
 27    int pre[MAXN];
 28    int cost = 0;
 29
 30    visited[s] = true;
 31    treeTag[s] = treeCnt;
 32
 33    for(int i=2; i<=n; i++)
 34    {
 35        lowcost[i] = G[s][i];
 36        pre[i] = s;
 37    }
 38
 39    for(int i=2; i<n; i++)
 40    {
 41        int temp = INF;
 42        int v = s;
 43
 44        for(int j=2; j<=n; j++)
 45        {
 46            if((!visited[j]) && (lowcost[j] < temp))
 47            {
 48                temp = lowcost[j];
 49                v = j;
 50            }
 51        }
 52        if(v == s)
 53        {
 54            return cost;
 55        }
 56
 57        treeTag[v] = treeCnt;
 58        visited[v] = true;
 59        cost += temp;
 60        MT[v][pre[v]] = true;                       //记录树中的边
 61        MT[pre[v]][v] = true;
 62
 63        for(int j=2; j<=n; j++)
 64        {
 65            if((!visited[j]) && (G[v][j] < lowcost[j]))
 66            {
 67                lowcost[j] = G[v][j];
 68                pre[j] = v;
 69            }
 70        }
 71    }
 72    return cost;
 73}
 74
 75int MST(int n)          //求最小生成森林
 76{
 77    int cost = 0;
 78    for(int i=2; i<=n; i++)
 79    {
 80        visited[i] = false;
 81    }
 82    visited[1] = true;
 83    treeTag[1] = 0;
 84    treeCnt = 0;
 85
 86    for(int i=1; i<=n; i++)
 87    {
 88        if(!visited[i])
 89        {
 90            ++treeCnt;
 91            cost += Prim(n,i);
 92        }
 93    }
 94    return cost;
 95}
 96
 97void CalMaxEdge(int n)             //DFS求出每个顶点到park(节点0)的最长边
 98{
 99    bool visited[MAXN];
100    queue<int> q;
101    int cur;
102    
103    for(int i=2; i<=n; i++)
104    {
105        visited[i] = false;
106    }
107    visited[1] = true;
108    maxEdge[1][0] = 0;
109
110    for(int j=2; j<=n; j++)
111    {
112        if(MT[1][j])
113        {
114            q.push(j);
115        }
116    }
117    while(!q.empty())
118    {
119        cur = q.front();
120        q.pop();
121        visited[cur] = true;
122        for(int j=2; j<=n; j++)
123        {
124            if((!visited[j]) && MT[cur][j])
125            {
126                q.push(j);
127                if(maxEdge[cur][0] > G[cur][j])
128                {
129                    maxEdge[j][0] = maxEdge[cur][0];
130                    maxEdge[j][1] = maxEdge[cur][1];
131                    maxEdge[j][2] = maxEdge[cur][2];
132                }
133                else
134                {
135                    maxEdge[j][0] = G[cur][j];
136                    maxEdge[j][1] = cur;
137                    maxEdge[j][2] = j;
138                }
139            }
140        }
141    }
142}
143
144int Slove(int n,int iLimit)         //求解问题的主要函数
145{
146    int minLen,v,temp;
147
148    int cost = MST(n);              //生成最小森林
149
150    if(treeCnt > iLimit)            //如果连通分支数大于度限制，则不存在满足度限制的最小生成树
151    {
152        return -1;
153    }
154
155    for(int i=1; i<=treeCnt; i++)           //加入park点，将上面生成的森林连成一棵生成树
156    {
157        minLen = INF;
158        v = -1;
159        for(int j=2; j<=n; j++)
160        {
161            if(treeTag[j] == i && G[1][j] < minLen)
162            {
163                minLen = G[j][1];
164                v = j;
165            }
166        }
167        MT[1][v] = true;
168        MT[v][1] = true;
169        cost += G[1][v];
170    }
171
172    CalMaxEdge(n);                        //求每个点到park点的最大边长
173
174    for(int i=treeCnt+1; i<=iLimit; i++)           //最小差额添删操作
175    {
176        minLen = INF;
177        v = -1;
178
179        for(int j=2; j<=n; j++)
180        {
181            if((G[1][j] != INF) && (!MT[1][j]))
182            {
183                temp = G[1][j] - maxEdge[j][0];                
184                if(minLen > temp)
185                {
186                    minLen = temp;
187                    v = j;
188                }
189            }
190        }
191        if(temp >= 0)                    //差额大于0，退出
192        {
193            return cost;
194        }
195        cost += minLen;
196
197        MT[1][v] = true;
198        MT[v][1] = true;
199        MT[maxEdge[v][1]][maxEdge[v][2]] = false;
200        MT[maxEdge[v][2]][maxEdge[v][1]] = false;
201
202        CalMaxEdge(n);                    //维护最大边数组
203    }
204    return cost;
205}
206
207int main()
208{
209    string nameA,nameB;
210    int n,s,d;
211    int num = 1;                         //节点数，包括park
212
213    for(int i=1; i<MAXN; i++)
214    {
215        for(int j=1; j<MAXN; j++)
216        {
217            G[i][j] = INF;
218            MT[i][j] = false;
219        }
220    }
221
222    cin>>n;
223    mTable["Park"] = 1;               //Park标记为1节点
224    for(int i=0; i<n; i++)            //输入数据，建图
225    {
226        cin>>nameA>>nameB>>d;
227        if(!mTable[nameA])
228        {
229            mTable[nameA] = ++num;
230        }
231        if(!mTable[nameB])
232        {
233            mTable[nameB] = ++num;
234        }
235        G[mTable[nameA]][mTable[nameB]] = d;
236        G[mTable[nameB]][mTable[nameA]] = d;
237    }
238    cin>>s;
239
240    cout<<"Total miles driven: "<<Slove(num,s)<<endl;
241
242    //system("pause");
243
244    return 0;
245}