最短路径
A1018. Public Bike Management
思路：
- 首先，为了编写代码，并得知所有结点中，哪个结点的点权(自行车数目)不够或者冗余，我们采取的方案是：把每个点的点权都减去Cmax/2，从而可以用点权的正负来直接判断当前车站是需要补给还是需要带走额外的车辆。
- 因为除了要输出最短路径以外，还要输出从PBMC携带出来的自行车数目和从问题车站Sp带回的自行车数目。
因此，我们采取的方案是：对每个顶点增加两个属性：
(1)从PBMC到当前车站必须携带的自行车数目Need;
(2)到达当前车站时手上多余的自行车数目Remain。
也就是说，
如果当前车站u的点权weight[u]为正，说明需要从该车站额外带走自行车，所以，新的Remain等于旧的Remain加上weight[u]。
如果当前车站u的点权weight[u]为负，说明当前车站需要补给的自行车数量为abs(weight[u])。此时，如果Remain大于0，就拿Remain来补给，但如果Remain补给后还是不够，剩下的只能从PBMC携带了，这时要记得更新Need，让Need加上这个不够的差值。
//--当前结点编号为id--
int id = tempPath[i];
//--如果点权大于0，说明需要带走一部分自行车--
if (weight[id] > 0)
{
remain += weight[id];
}
//--如果点权不超过0，需要补给--
else
{
//--如果当前持有量remain足够补给--
if (remain > abs(weight[id]))
{
//--那么就用当前持有量remain减去需要补给的量--
remain -= abs(weight[id]);
}
//--如果当前持有量remain不够补给--
else
{
//--不够的部分从PBMC携带--
need += abs(weight[id]) - remain;
//--当前持有的自行车全部用来补给，所以归0--
remain = 0;
}
}
- 这道题需要先使用Dijkstra算法求出所有的最短路径。再使用DFS算法从这些最短路径中选出need最小的，如果need相同，则选择remain最小的。
注意点：
- 大家要注意一点：从起点PBMC出发到达问题站点Sp的过程中，就需要调整路径上所有站点的状态至Perfect。
- 这道题不能单单的使用Dijkstra算法来搞定，因为minNeed和minRemain在路径上的传递不满足最优子结构，因为它不是简单的相加过程。
事实上，只有当所有路径都确定后，才能去选择最小的need和最小的remain。
代码逻辑：
- 这次定义的新变量中，有3个vector变量。pre[]前驱和tempPath, path临时路径和最优路径。
》- 先看main()函数，首先输入车站的最大容量Cmax，顶点数n，问题站点Sp，边数m。然后使用邻接矩阵初始化图G，图G的初值均为INF。接下来，在输入点权的时候减去最大容量的一半Cmax/2。最后，更新边权G[u][v]，而且要手动保证G[v][u] = G[u][v]。
- 这一步开始，就直接进入到了Dijkstra算法和DFS算法。
这里我们让起点s作为参数传入Dijkstra算法，这里起点的编号为0。
紧接着，将问题站点Sp作为参数传入DFS算法。- Dijkstra算法：数组d[]记录最短距离。
第一步，初始化d[]，初值均为INF。接下来，定义前驱结点pre[]，遍历n个结点，使pre[i] = i;
第二步，遍历n个结点，找到未访问结点中d[]最小的。特殊情况：没有小于INF的d[u]，说明剩下的顶点和起点s不连通。注意：如果顶点u已经访问，要记得将u的访问状态更新为true。
第三步，重新遍历n个顶点。这次，如果顶点v未被访问，而且顶点u和v之间可到达。我们就看以u为中介点，能否使最短距离d[v]更小，
可以的话，便更新。注意：更新d[v]的同时，还要将前驱结点数组pre[]先清空，再把顶点u加到pre[v]中(本来初始化中，pre[v]=v，现在pre[v]=u，也就是说v的前驱顶点是u)。
不可以的话，那么如果以u为中介点，最短距离和d[v]相同。那么不清空pre[v]，而是直接将顶点u加入到pre[v]中，也就是，顶点v的前驱顶点有2个，一个是v，后面的是u。
注意：这里需要注意的一点是，昨天做的题可以在更新d[v]的时候，可以同步更新最大点权之和w[]和最短路径条数num[]，是因为w[]和num[]在路径上的传递满足最优子结构。然而这道题，我们只是同步更新了顶点v的前驱顶点u。没有同步更新最少携带的数目minNeed和最少带回的数目minRemain。因为这俩不满足最优子结构，求解并不是简单的相加过程。只有在所有路径确定后，才可以去选择最小的need和最小的remain。- DFS算法：
我们以问题站点Sp作为参数传入DFS(int v)中。
如果Sp是起点(0号顶点)(不一定一开始就进入v=0这个if{}中，因为DFS()在不断递归调用，递归到PBMC起点了)，则向临时路径tempPath中添加该顶点Sp(起点)。然后倒着枚举tempPath中的每个顶点i。看看这个站点i的点权是否大于0——
如果点权大于0，则带走特定数量的自行车。
如果点权不超过0，说明需要补给，如果当前持有量够(可能已经经过一个站点了，从那个站点中带出来了一些)，就拿来补给。如果不够，就说明需要从PBMC中带。
当枚举完该tempPath临时路径的所有站点后，我们的remain和need都得到了更新，如果新的remain和need比minNeed和minRemain更优，则更新minNeed和minRemain，同时，将当前这个tempPath临时路径更新为最优路径path。最后，将tempPath中的尾元素(也就是起点)删除掉。返回return。
总结一下：当DFS(s)中的顶点为起点时，说明已经倒着递归到了最后一步。
假如，当前DFS(v)中的结点v不是起点，那么就将顶点v加入到tempPath中，然后顺着枚举顶点v的每个前驱顶点pre[v][i]。最后递归结束，不断地返回过程中，不断地删除tempPath临时路径的尾元素。(原因是tempPath可能会不断地新添顶点，如果不删除干净，可能会计算错误)- 输出答案：当Dijkstra算法和DFS算法均进行完后，输出minNeed和minRemain。值得一提的是，在输出仿真最优路径的时候，需要倒着枚举最优路径path的每一个顶点(原因是DFS()在递归的时候，是从问题站点(i.e. 目的地)开始，在起点(i.e.PBMC起点))结束的。
完整代码：
//--s为起点--
void Dijkstra(int s)
{
fill(d, d + MAXV, INF);
for (int i = 0; i <= n; i++)
{
pre[i].push_back(i);
}
d[s] = 0;
for (int i = 0; i <= n; i++) // 这里写成(i<n)或(i<=n)结果没有区别
// 也就是循环n次和循环n+1次没有区别
{
int u = -1, MIN = INF;
//--找到未访问的顶点中d[]最小的--
for (int j = 0; j <= n; j++)
{
if (vis[j] == false && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
//--找不到小于INF的d[u]，说明剩下的顶点和起点s不连通--
if (u == -1) return;
//--标记u为已访问--
vis[u] = true;
for (int v = 0; v <= n; v++)
{
//--如果v未访问，并且u能到达v--
if (vis[v] == false && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[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);
}
}
}
}
}
void DFS(int v)
{
if (v == 0)
{
//--递归边界，叶子结点--
tempPath.push_back(v);
//--路径上tempPath上需要携带的数目，需要带回的数目--
int need = 0, remain = 0;
//--此处必须倒着枚举--
for (int i = tempPath.size() - 1; i >= 0; i--)
{
//--当前结点编号为id--
int id = tempPath[i];
//--如果点权大于0，说明需要带走一部分自行车--
if (weight[id] > 0)
{
remain += weight[id];
}
//--如果点权不超过0，需要补给--
else
{
//--如果当前持有量remain足够补给--
if (remain > abs(weight[id]))
{
//--那么就用当前持有量remain减去需要补给的量--
remain -= abs(weight[id]);
}
//--如果当前持有量remain不够补给--
else
{
//--不够的部分从PBMC携带--
need += abs(weight[id]) - remain;
//--当前持有的自行车全部用来补给，所以归0--
remain = 0;
}
}
}
//--如果需要从PBMC携带的自行车数目可以更少--
if (need < minNeed)
{
//--那么就优化minNeed--
minNeed = need;
//--同时覆盖minRemain--
minRemain = remain;
//--还要覆盖最优路径path--
path = tempPath;
}
//--如果携带数目相同，带回数目变少--
else if (need == minNeed && remain < minRemain)
{
//--那么就优化minRemain--
minRemain = remain;
//--还要覆盖最优路劲path--
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] + MAXV * MAXV, 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];
}
Dijkstra(0);
DFS(Sp);
//---输出需要从PBMC携带的最少bike数目---
printf("%d ", minNeed);
//---输出仿真最优路径---
for (int i = path.size() - 1; i >= 0; i--)
{
printf("%d", path[i]);
if (i > 0) printf("->");
}
//---输出需要从问题站Sp带回的最少bike数目---
printf(" %d", minRemain);
return 0;
}
A1072. Gas Station
思路：
- 首先解决的是顶点的编号问题。我们通过写一个getID()函数来搞定。
- 枚举每个加油站，使用Dijkstra算法来得到所有居民房距离该加油站的最短距离。因为本题中所有的无向边都是真实存在的，所以Dijkstra算法中，顶点编号的范围应该是1~(n+m)。
- 在我们通过Dijkstra算法得到某个加油站的数组d[maxv]后，还需要获取其中的最小元素(也就是加油站与居民房的所有最短距离中的最近距离)。也许大家会有疑惑，我们通过D算法求得的，是所有居民房距离该加油站的最短距离。还要求所有居民房与加油站的平均距离。
注意点：
- D算法要重复多次，所以要在开头，也就是每次执行算法前都要重置vis数组为false, d[]数组为INF。
- 因为我们会定义一个变量最大的最近距离，因为是求最大，所以其初值必须设为一个较小的数(比如-1)。
(怎么理解这个最大的最近距离呢？先考虑加油站G1，找到离G1最近的居民房的距离。然后在看G2 G3等等一系列加油站，看看G2 G3离最近的居民房的距离有多大，在加油站G这个维度上，选一个最大的。在枚举单个加油站Gi的时候，选择距离最小的。)
那么就是说，之前d[]数组，求得就是枚举每一个加油站，得到d[MAXV]则为G1离每个最近居民房的距离。然后在这里面，找一个最小的。这个最小的，就是该加油站与居民房的最近距离。
也可以说，一开始是在寻找距离某个特定加油站G最近(小)的那个居民房是多少号，距离又是多少。然后再对比每个加油站G与其最近的据民房的最近距离，这次取最大的。
代码逻辑：
- 首先看main()函数，为了将加油站ID可以顺利输入，我们定义顶点编号的类型为char型数组，来表示字符串(用string应该也可以)。
- 还是main()函数中，枚举所有的加油站，范围从n+1到n+m。枚举过程中，先通过D算法求出d[]数组，也就是距离第n+i号加油站，每一个居民房与它的最短距离。然后，得到某个特定加油站的d[]数组后，再针对该加油站枚举所有的居民房(当然这个for循环是嵌套在上个for循环中的)。
在这第二个枚举所有的据民房中，我们要求的是——
针对于某个特定加油站G，离其最近的居民房的距离和所有居民房与该加油站的平均距离。
跳出第二个枚举所有居民房的循环后，这时我们已经得到了针对于某个加油站，所有居民房与它的平均距离，还有离它最近的呢个居民房。
接下来，看的是，该加油站与所有居民房的距离中，是否有哪个居民房离它的距离大于了DS，如果有，则直接跳过该加油站，进入下一个加油站（continue）。
如果没有出现大于DS的，则更新最大的最近距离(ansDis)，如果到了后面加油站多了起来，最大的最近距离一样，则更新最小的平均距离，谁的平均距离最小，则选择哪个加油站。
注意：minDis是最近距离，ansDis是最大的最近距离。因为minDis是求最小值，所以minDis的初值是INF。求解代码是这样(注意是d[j]<minDis，是小于号，看看d[j]是否小于minDis，如果小于当前的minDis，就更新minDis)：
double minDis = INF, avg = 0;
//--更新当前最大的最近距离--
if (d[j] < minDis) minDis = d[j];
然而，求ansDis是最大值，所以ansDis初值为-1。if判断中，则是大于号(看看minDis是否大于ansDis，如果大于当前的ansDis，就更新ansDis)——
double ansDis = -1, ansAvg = INF;
int ansID = -1;
//--更新最大的最近距离--
if (minDis > ansDis)
{
ansID = i;
ansDis = minDis;
ansAvg = avg;
}
完整代码如下：
//---Dijkstra算法求所有顶点到起点s的最短距离---
void Dijkstra(int s)
{
memset(vis, false, sizeof(vis));
fill(d, d + MAXV, INF);
d[s] = 0;
for (int i = 0; i < n + m; i++)
{
int u = -1, MIN = INF;
for (int j = 1; j <= n + m; j++)
{
if (vis[j] == false && d[j] < MIN)
{
u = j;
MIN = d[j];
}
}
if (u == -1) return;
vis[u] = true;
for (int v = 1; v <= n + m; v++)
{
if (vis[v] == false && G[u][v] != INF)
{
if (d[u] + G[u][v] < d[v])
{
d[v] = d[u] + G[u][v];
}
}
}
}
}
//---将str[]转换为数字，若str是数字，则返回本身---
//---否则，返回去掉G之后的数，并加上n---
int getID(char str[])
{
int i = 0, len = strlen(str), ID = 0;
while (i < len)
{
//--只要不是G，就转换为数字--
if (str[i] != 'G')
{
ID = ID * 10 + (str[i] - '0');
}
i++;
}
//--首位如果是G，返回n+ID--
if (str[0] == 'G') return n + ID;
//--首位不是G，返回ID--
else return ID;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &k, &DS);
//--u和v表示一条road的左右端点，w表示边权--
int u, v, w;
char city1[5], city2[5]; // 这里的字符串还是用char型数组来定义的
fill(G[0], G[0] + MAXV * MAXV, INF);
for (int i = 0; i < k; i++)
{
//--以字符串的形式读入城市编号--
scanf("%s %s %d", city1, city2, &w);
u = getID(city1);
v = getID(city2);
//--边权--
G[v][u] = G[u][v] = w;
}
//--ansDis存放最大的最近距离--
//--ansAvg存放最小的平均距离--
//--ansID存放最终的加油站ID--
double ansDis = -1, ansAvg = INF;
int ansID = -1;
//--枚举所有的加油站--
for (int i = n + 1; i <= n + m; i++)
{
//---minDis为当前最大的最近距离，avg为平均距离---
double minDis = INF, avg = 0;
//---进行Dijkstra算法，求出d[]数组---
Dijkstra(i);
//---枚举所有据民房---
//---求出当前的minDis和avg---
for (int j = 1; j <= n; j++)
{
//--存在距离大于DS的居民房，直接跳出--
if (d[j] > DS)
{
minDis = -1;
break;
}
//--更新当前最大的最近距离--
if (d[j] < minDis) minDis = d[j];
//--获取平均距离--
avg += 1.0 * d[j] / n;
}
//--如果存在距离大于DS的居民房，则跳过该加油站--
if (minDis == -1) continue;
//--更新最大的最近距离--
if (minDis > ansDis)
{
ansID = i;
ansDis = minDis;
ansAvg = avg;
}
//--更新最小平均距离--
else if (minDis == ansDis && avg < ansAvg)
{
ansID = i;
ansAvg = avg;
}
}
//--无解--
if (ansID == -1) printf("No Solution\n");
else
{
printf("G%d\n", ansID - n);
printf("%.1f %.1f\n", ansDis, ansAvg);
}
return 0;
}
这次没有详细说D算法，因为D算法这次唯二的不同就是——
- 函数的头2步，分别是对vis[]和d[]数组的重新赋值(d[s]=0是都有的)
- 枚举范围是n+m
