pat 1018 Public Bike Management

一点教训

1018

说明:
被注释的代码是我自己写的,只能过其中三个case,原因是没有进行比较(误认为minNeed和minRemain满足最优子结构),单纯的使用Dijstra算法。

在Ac的代码中,有几个值得学习的思路:

  1. 当有多条路径需要记录时,可以选用vector<int> pre[MAX]来记录,而不是死板硬套的int pre[MAX]
  2. 本题不能只使用Dijstra来解决,因为minNeed和minRemain在路径上传递的时候不满足最优子结构(不是简单的相加过程),也就是说,只有当所有的路径都确定之后,才能选择最小的need和最小的remain
  3. DFS用来遍历所有权值相等的路径时候,不需要关心是否会出现“乱序“的情况
1
2
3
4
for(int i =0 ; i < pre[v].size() ; ++i)
{
DFS(pre[v][i]);//分别遍历每条路径
}
  1. 带有权值的结构一般使用邻接矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
/*#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1010
#define INF 1000000000
using namespace std;
int n , m , cmax , sp;
int weight[MAX] = {0};
struct Edge
{
int id , dis;
};
vector<Edge> G[MAX];
bool vis[MAX] = {false};
int d[MAX];
int w[MAX] = {0};
bool isneed = true;
int pre[MAX] = {0};
int need = 0 , sent= 0;
void Dijstra(int s)
{
fill(d , d+MAX , INF);
fill(pre , pre+MAX , 0);
fill(vis , vis+MAX , false);
fill(w , w+MAX , 0);
d[s] = 0;
int i , j;
for(i = 0 ; i <= n ; ++i)
{
int u = -1 , min = INF;
for(j = 0 ; j <= n ; ++j)
{
if(vis[j] == false && min > d[j])
{
u = j;
min = d[j];
}
}
if(u == -1)
return;
vis[u] = true;
if(u == sp)
{
//cout<<sent<<endl;
if(w[u] <= 0)
{
isneed = true;
need = w[u] + cmax/2;
need = cmax/2 - need;
}
else
{
isneed = false;
need = w[u];
}
break;
}
for(j = 0 ; j < G[u].size() ; ++j)
{
int v = G[u][j].id;
if(vis[v] == false)
{
if(d[u] + G[u][j].dis < d[v])
{
d[v] = d[u] + G[u][j].dis;
if(weight[v] >= cmax/2 || v == sp)
{
w[v] = w[u] + (weight[v] - cmax/2);
}
else
{
sent += cmax/2 - weight[v];
}
pre[v] = u;
}
else if(d[u] + G[u][j].dis == d[v])
{
if(w[v] < w[u]+ (weight[v] - cmax/2))
{
if(weight[v] >= cmax/2 || v==sp)
{
w[v] = w[u]+(weight[v] - cmax/2);
}
else
{
sent += cmax/2 - weight[v];
}
pre[v] = u;
}
}
}
}
}
}
//回溯路径
void DFS(int s , int v)
{
if(s == v)
{
cout<<" "<<v;
return;
}
DFS(s , pre[v]);
cout<<"->"<<v;
}
int main()
{
cin>>cmax>>n>>sp>>m;
int i;
fill(weight , weight + MAX , 0);
for(i = 1 ; i <= n ; ++i)
{
cin>>weight[i];
}
Edge temp;
int a , b , dis;
for(i = 0 ; i < m ; ++i)
{
cin>>a>>b>>dis;
temp.id = b;
temp.dis = dis;
G[a].push_back(temp);
temp.id = a;
G[b].push_back(temp);
}
Dijstra(0);
if(isneed)
{
sent = need;
}
cout<<sent;
DFS(0 , sp);
if(isneed)
cout<<" 0";
else
cout<<" "<<need;
return 0;
}
*/
/*
本题可以使用Dijstra+DFS的写法求解。具体做法是:
先用Dji求出所有的最短路径,然后用DFS从这些最短路径中选出need最小的(need相同时选择remain最小的)。
最短路径的条数既可以在Dji中顺便求出,也可以在DFS中边界条件处进行累计
*/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 510;
const int INF = 1000000000;
//n为顶点数,m为边数,Cmax为最大容量,sp为问题节点
//G为邻接矩阵,weight为点权,d[]记录最短距离
//minNeed记录最少携带数目,minRemain记录最少带回的数目
int n , m , Cmax , Sp , numPath = 0 , G[MAX][MAX] , weight[MAX];
int d[MAX] ,minNeed = INF , minRemain = INF;
bool vis[MAX] ={false};
vector<int> pre[MAX];//前驱
vector<int> tempPath , path;//临时路径,最优路径
void Dijstra(int s)
{
fill(d , d+MAX , INF);
for(int i = 0 ; i <= n ; ++i)
{
pre[i].push_back(i);
}
d[s] = 0;
for(int i = 0 ; i< n ; ++i)
{
int u = -1 , min = INF;
for(int j = 0 ; j <= n ; ++j)
{
if(vis[j] == false && min > d[j])
{
u = j;
min = d[j];
}
}
if(u == -1)
return;
vis[u] = true;
for(int v = 0 ; v <= n ; ++v)
{
if(vis[v] == false && G[u][v] != INF)
{
if(d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
pre[v].clear();//在记录之前清除残余
pre[v].push_back(u);
}
else if(d[u] + G[u][v] == d[v])
{
pre[v].push_back(u);//记录多条路径使用vector,好!
}
}
}
}
}
void DFS(int v)
{
if(v == 0)//递归边界,叶子节点(0 为根节点)
{
tempPath.push_back(v);
//路径tempPath上需要携带的数目、需要带回的数目
int need = 0 , remain = 0;
for(int i = tempPath.size() -1 ; i >= 0 ; --i)
{
int id = tempPath[i];
if(weight[id] > 0)
{
remain += weight[id];
}
else
{
if(remain > abs(weight[id]))
{
remain -= abs(weight[id]);
}
else
{
need += abs(weight[id]) - remain;
remain = 0;
}
}
}
if(need < minNeed)
{
minNeed = need;
minRemain = remain;
path = tempPath;
}else if(need == minNeed && remain < minRemain)
{
minRemain = remain;
path = tempPath;
}
tempPath.pop_back();
return;
}
tempPath.push_back(v);
for(int i =0 ; i < pre[v].size() ; ++i)
{
DFS(pre[v][i]);//分别遍历每条路径
}
tempPath.pop_back();
}
int main()
{
scanf("%d%d%d%d" , &Cmax , &n , &Sp , &m);
int u , v;
fill(G[0] , G[0] + MAX*MAX , INF);
for(int i =1 ; i <= n ; ++i)
{
scanf("%d" , &weight[i]);
weight[i] -= Cmax/2;
}
for(int i = 0 ; i < m ; ++i)
{
scanf("%d%d" , &u , &v);
scanf("%d" , &G[u][v]);
G[v][u] = G[u][v];
}
Dijstra(0);
DFS(Sp);
printf("%d " , minNeed);
for(int i = path.size() - 1; i >= 0 ; --i)
{
printf("%d" , path[i]);
if(i >0)
printf("->");
}
printf(" %d" , minRemain);
return 0;
}

热评文章