题意:给出若干个小矮人的家和一个公园,这些小矮人到公园去聚会,题中给了若干条路线,还有每条路线的长度,在这些路线上穿行需要开车,但是公园只可容纳一定数量的汽车,小矮人可以部分聚集到一起再一起开车到公园,求需要行驶的最短距离。
思路:求最小生成树,其中某一个节点的度是限制的,即度限制最小生成树。
解法:
(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}