PAT甲级1018 Public Bike Management (30分)|C++实现

一、题目描述

原题链接

Input Specification:

​​Output Specification:

Sample Input:

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

Sample Output:

3 0->2->3 0

二、解题思路

算是一道比较复杂的30分题，但是基本思路还算清晰，用Dijkstra算法找最短路径，用一个vector的数组来记录最短路径中每个点的前一个点，用dfs从后往前检索，记录路径，寻找需要回收或者需要发放的自行车最少的一条。思路就是这样，但是具体实现的细节非常多，代码也很长，这些细节都写在代码的注释中了。

三、AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int INF = 99999999;
int cmax, n, sp, m; //一个地点最多存放的车辆数，站点数，问题站点，图的边数
int minNeed = INF, minback = INF; //最少需要的车辆，最少回收的车辆
int e[510][510], dis[510], weight[510]; //邻接矩阵，到每个点的最短距离，每个顶点当前的车辆数-cmax/2
bool visit[510]; //Dijkstra算法中是否已经更新到最短值的标记
vector<int> pre[510], path, temppath;
void dfs(int v)
{
  temppath.push_back(v);
  if(v == 0)
  {
    int need=0, back=0;
    for(int i=temppath.size()-1; i>=0; i--)
    {
      int id = temppath[i];
      if(weight[id] > 0)    //说明应该从这个站点回收自行车
        back += weight[id];
      else
      {
        if(back > -weight[id])  //说明已经回收的车辆数大于需要给这个站点的车辆数
          back += weight[id];   //注意这里weight[id]是个负数，所以实际上是回收的车辆减去给这个站点的车辆
        else    //说明总体需要我们从起点运车
        {
          need += (-weight[id] - back);
          back = 0; //把需要还的车辆数设置为0
        }
      }
    }
    if(need < minNeed)  //如果当前的路径需要的车辆数更加少
    {
      minNeed = need;
      minback = back;
      path = temppath;
    }
    else if(need == minNeed && back < minback)  //当前的路径回收的车辆更加少
    {
      minback = back;
      path = temppath;
    }
    temppath.pop_back();    //退回到之前的顶点
    return;
  }
  for(int i=0; i<pre[v].size(); i++)
    dfs(pre[v][i]); //对该点的前面所有点（具有相同最短距离的点）进行dfs
  temppath.pop_back();  //退回之前的顶点
}
int main()
{
  fill(e[0], e[0]+510*510, INF);
  fill(dis, dis + 510, INF);
  scanf("%d%d%d%d", &cmax, &n, &sp, &m);
  for(int i=1; i<=n; i++)
  {
    scanf("%d", &weight[i]);
    weight[i] = weight[i] - cmax/2;
  }
  for(int i=0; i<m; i++)
  {
    int a, b;
    scanf("%d%d", &a, &b);
    scanf("%d", &e[a][b]);
    e[b][a] = e[a][b];
  }
  dis[0] = 0;   //开始Dijkstra算法
  for(int i=0; i<=n; i++)
  {
    int u=-1, minn = INF;
    for(int j=0; j<=n; j++)
    {
      if(visit[j] == false && dis[j] < minn)
      {
        u = j;
        minn = dis[j];
      }
    }
    if(u == -1)	break;
    visit[u] = true;
    for(int v=0; v<=n; v++)
    {
      if(visit[v] == false && e[u][v] != INF)
      {
        if(dis[v] > dis[u] + e[u][v])
        {
          dis[v] = dis[u]+e[u][v];
          pre[v].clear();
          pre[v].push_back(u);
        }
        else if(dis[v] == dis[u] + e[u][v])
          pre[v].push_back(u);
      }
    }
  } //Dijkstra算法结束
  dfs(sp);
  printf("%d 0", minNeed);
  for(int i=path.size()-2; i>=0; i--)   //因为我们把0放在前面输出了，所以这里是从size()-2开始循环
    printf("->%d", path[i]);
  printf(" %d", minback);
}