1018 Public Bike Management

  1. 1. Public Bike Management
  2. 2. 思路
  3. 3. 一点小想法

Public Bike Management

1018 Public Bike Management

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

The above figure illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S​3​​, we have 2 different shortest paths:

  1. PBMC -> S​1​​ -> S​3​​. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S​1​​ and then take 5 bikes to S​3​​, so that both stations will be in perfect conditions.

  2. PBMC -> S​2​​ -> S​3​​. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

我是图

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: C​max​​ (≤100), always an even number, is the maximum capacity of each station; N (≤500), the total number of stations; S​p​​, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers C​i​​ (i=1,⋯,N) where each C​i​​ is the current number of bikes at S​i​​ respectively. Then M lines follow, each contains 3 numbers: S​i​​, S​j​​, and T​ij​​ which describe the time T​ij​​ taken to move betwen stations S​i​​ and S​j​​. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0−>S​1​​−>⋯−>S​p​​. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of S​p​​ is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input:

1
2
3
4
5
6
7
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1

Sample Output:

1
3 0->2->3 0

题目大意:
公共自行车站点的自行车数量是半满的时候称为完美.不完美的站点就需要调度.给定起点和终点,找到最短的一条路线,并把沿途经过的站点全部调度为完美.如果有多条路线存在,选择从起点带出自行车最小的那一条.最后输出从起点带出的自行车数,路线,从终点带回的自行车数.

思路

单源最短路径问题dijkstra是跑不掉了.问题的关键在于,当松弛的对象v的最短路径预期dist[v]和当前最短路径于权值的和dist[min]+edge(min,v)相等时候的取舍.
一个简单的想法是,出现一致时,计算最短路上平均节点的点权,取最大的那一条.很不幸的是,dijkstra执行过程中并不知道所要比较的两条最短路的长度.

参考了其他人的思路,与其在还未生成最短路径时想办法取舍,不如等到所有的最短路径都求出来以后再去选最优的那一条.原版算法中记录前驱结点的int path[]就要改成vector<int> pre[]了.松弛成功时,清空path[i],放入min.权值相同时,放入min.

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
void dijkstra()
{
	bool visited[504];
	fill(visited,visited+n+1,false);
	fill(estimate,estimate+n+1,inf);
	estimate[0]=0;
	while(true)
	{
		int min=-1;
		int minn=inf;
		for(int i=0;i<=n;i++)
		{
			if(estimate[i]<minn&&visited[i]==false)
			{
				minn=estimate[i];
				min=i;
			}
		}
		if(minn==inf) break;
		visited[min]=true;
	
		for(int i=0;i<=n;i++)
		{
			if(t[min][i]!=-1&&visited[i]==false)
			{
				if(estimate[i]>estimate[min]+t[min][i])
				{
					estimate[i]=estimate[min]+t[min][i];
					path[i].clear();
					path[i].push_back(min);
				
				} else if(estimate[i]==estimate[min]+t[min][i])
				{
					path[i].push_back(min);
				}
			}
		}
	}
}

跑完dijkstra,path[i]的笛卡尔积就是所有的最短路径.

现在问题转化为,给定好几条路径,如何选出最优的那一条.dfs帮了大忙.

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
void dfs(int v)
{
	temp_path.push_back(v);
	if(v==0)
	{
		int need=0;
		int back=0;
		for(int i=temp_path.size()-1;i>=0;i--)
		{
			int id=temp_path[i];
			if(bycicle[id]>0)
			{
				back+=bycicle[id];
			} else
			{
				if(back>(0-bycicle[id]))
				{
					back+=bycicle[id];
				} else
				{
					need+=((0-bycicle[id])-back);
					back=0;
				}
			}
		}
		if(need<min_need)
		{
			min_need=need;
			min_back=back;
			min_path=temp_path;
		} else if(need==min_need&&back<min_back)
		{
			min_back=back;
			min_path=temp_path;
		}
		temp_path.pop_back();
		return;
	}
	else{
				
		for(auto i:path[v])
		{
			dfs(i);
		}
	}
	temp_path.pop_back();
}

进入dfs后二话不说先将当前节点放入temp_path,在返回之前再将其弹出.这保证了,调用dfs(sp)后,只要v是起点,temp_path就是一条完整的路径(倒序).倒过来就能推出带出和带回的自行车数.

  • 当节点的自行车数与完美状态的差值bicycle[i]=s[i]-cmax/2为正时,在离开该节点时需要带走这么多车子.back+=bicycle[i].
  • 当bicycle[i]为负时,考虑两种情况.
    • back比bicycle[i]的绝对值大时,表示携带的自行车比当前节点要多.只需分给该节点|bibycle[i]|这么多的自行车即可达成完美.back+=bicycle[i]
    • 当back比bicycle[i]的绝对值要小时,表示携带的自行车不够分,需要从起点携带.两者的差值就是所需的车辆数.need+=(0-bicycle[i])-back,携带的车辆数置零back=0

选出need和back最小的路线即可.

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
#include "cstdio"
#include "vector"
#include "iostream"
using namespace std;
int cmax;
int n;
int sp;
int m;
int bycicle[504];
int t[504][504];
const int inf = 0xFFFFFFF;
vector<int> path[504];
int estimate[504];
vector<int> min_path;
int min_need=inf;
int min_back=inf;
vector<int> temp_path;
void dfs(int v)
{
	temp_path.push_back(v);
	if(v==0)
	{
		int need=0;
		int back=0;
		for(int i=temp_path.size()-1;i>=0;i--)
		{
			int id=temp_path[i];
			if(bycicle[id]>0)
			{
				back+=bycicle[id];
			} else
			{
				if(back>(0-bycicle[id]))
				{
					back+=bycicle[id];
				} else
				{
					need+=((0-bycicle[id])-back);
					back=0;
				}
			}
		}
		if(need<min_need)
		{
			min_need=need;
			min_back=back;
			min_path=temp_path;
		} else if(need==min_need&&back<min_back)
		{
			min_back=back;
			min_path=temp_path;
		}
		temp_path.pop_back();
		return;
	}
	else{
				
		for(auto i:path[v])
		{
			dfs(i);
		}
	}
	temp_path.pop_back();
}
void dijkstra()
{
	bool visited[504];
	fill(visited,visited+n+1,false);
	fill(estimate,estimate+n+1,inf);
	estimate[0]=0;
	while(true)
	{
		int min=-1;
		int minn=inf;
		for(int i=0;i<=n;i++)
		{
			if(estimate[i]<minn&&visited[i]==false)
			{
				minn=estimate[i];
				min=i;
			}
		}
		if(minn==inf) break;
		visited[min]=true;
	
		for(int i=0;i<=n;i++)
		{
			if(t[min][i]!=-1&&visited[i]==false)
			{
				if(estimate[i]>estimate[min]+t[min][i])
				{
					estimate[i]=estimate[min]+t[min][i];
					path[i].clear();
					path[i].push_back(min);
				
				} else if(estimate[i]==estimate[min]+t[min][i])
				{
					path[i].push_back(min);
				}
			}
		}
	}
}
int main()
{
	cin>>cmax>>n>>sp>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",bycicle+i);
		bycicle[i]-=cmax/2;
	}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) t[i][j]=-1;
	for(int i=0;i<m;i++)
	{
		int si,sj,tij;
		scanf("%d %d %d",&si,&sj,&tij);
		t[si][sj]=tij;
		t[sj][si]=tij;
	}
	dijkstra();
	dfs(sp);
	printf("%d 0",min_need);
	for(int i=min_path.size()-2;i>=0;i--)
	{
		printf("->%d",min_path[i]);
	}
	printf(" %d\n",min_back);
	
	
}

一点小想法

  • 用dfs外加辅助存储可以实现类似笛卡尔积的效果.比排列组合要方便不少
  • 经典算法之所以经典的原因在于,很多问题可以用经典算法的变体解决.适用面大,所以经典.
  • 在计算back和need时又用到了递推.给递推打个星⭐
PAT
prev： next：