PAT图笔记

算法最短路径图的遍历

字数统计: 7.3k阅读时长: 36 min

 2023/08/20 

PAT考试图相关笔记

图的遍历

[1013] Battle Over Cities

图的遍历，统计连通分量的个数，DFS

题目

给定一个无向图并规定，当删除图中的某个顶点时，将会同时把与之连接的边一起删除。接下来给出 k 个查询，每个查询给出一个欲删除的顶点编号，求删除该顶点(和与其连接的边)后需要增加多少条边，才能使图变为连通(注:k 次查询均在原图上进行)。

分析与注意点

添加的最少的路线，就是他们的连通分量数-1，因为当a个互相分⽴的连通分量需要变为连通图的时候，只需要添加a-1个路线，就能让他们相连。所以这道题就是求去除了某个结点之后其他的图所拥有的连通分量数；
使⽤邻接矩阵存储，对于每⼀个被占领的城市，去除这个城市结点，就是把它标记为已经访问过，这样在深度优先遍历的时候，对于所有未访问的结点进⾏遍历，就能求到所有的连通分量的个数；

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
vector<vector<int>> G, temp;

void dfs(int a) {
  temp[a][a] = INT_MAX;
  for (int i = 1; i <= n; i++) {
    if (temp[i][i] == 1 && temp[a][i] != INT_MAX) {
      dfs(i);
    }
  }
  return;
}

int main() {
  cin >> n >> m >> k;
  G.resize(n + 1, vector<int>(n + 1, INT_MAX));
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    G[a][b] = 1;
    G[b][a] = 1;
  }
  for (int i = 0; i < k; i++) {
    int cur;
    cin >> cur;
    temp = G;
    for (int j = 1; j <= n; j++) {
      temp[j][j] = 1;
      if (temp[j][cur] != INT_MAX) {
        temp[j][cur] = INT_MAX;
        temp[cur][j] = INT_MAX;
      }
    }
    int ans = 0;
    for (int i = 1; i <=n; i++) {
      if (temp[i][i] == 1) {
        dfs(i);
        ans++;
      }
    }
    cout << ans - 1;
    if (i < k - 1)  cout << endl;
  }
  return 0;
}

[1021] Deepest Root

图的遍历，统计连通分量的个数，DFS，树的最高深度

题目

给出n个结点（1~n）之间的n条边，问是否能构成⼀棵树，如果不能构成则输出它有的连通分量个数，如果能构成⼀棵树，输出能构成最深的树的⾼度时，树的根结点。如果有多个，按照从⼩到⼤输出。

分析与注意点

⾸先深度优先搜索判断它有⼏个连通分量。如果有多个，那就输出Error: x components，如果只有⼀个，就两次深度优先搜索，先从⼀个结点dfs后保留最⾼⾼度拥有的结点们，然后从这些结点中的其中任意⼀个开始dfs得到最⾼⾼度的结点们，这两个结点集合的并集就是所求.

代码

#include <bits/stdc++.h>
using namespace std;
int n, d = 0, maxD = 0;
vector<int> vis, ans;
vector<vector<int>> G;

void dfs(int a, int depth) {
  vis[a] = true;
  d = max(d, depth);
  for (int i = 0; i < G[a].size(); i++) {
    if (vis[G[a][i]] == false) {
      dfs(G[a][i], depth + 1);
    }
  }
  return;
}

int main() {
  cin >> n;
  G.resize(n + 1);
  vis.resize(n + 1, false);
  for (int i = 0; i < n-1; i++) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (vis[i] == false) {
      dfs(i, 1);
      cnt++;
    }
  }
  if (cnt > 1)
    cout << "Error: " << cnt << " components";
  else {
    for (int i = 1; i <= n; i++) {
      // 注意这里不能用vis.resize(n + 1, false)
      // 大小已经为(n + 1)，不会进行重置，无法改变vis的值
      fill(vis.begin(), vis.end(), false);
      d = 0;
      dfs(i, 1);
      if (d >= maxD) {
        if (d > maxD) {
          ans.clear();
          maxD = d;
        }
        ans.push_back(i);
      }
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
      cout << ans[i];
      if (i != ans.size() - 1)
        cout << endl;
    }
  }
  return 0;
}

[1034] Head of a Gang

图的遍历，DFS

题目

给出若干人之间的通话长度(视为无向边)，按照这些通话将他们分为若干个组。每个组的总边权设为该组内的所有通话的长度之和，而每个人的点权设为该人参与的通话长度之和。现在给定一个阙值 K，且只要一个组的总边权超过 K，并满足成员人数超过 2，则将该组视为“犯罪团伙(Gang)”，而该组内点权最大的人视为头目。要求输出“犯罪团伙”的个数,并按头目姓名字典序从小到大的顺序输出每个“犯罪团伙”的头目姓名和成员人数。

分析与注意点

首先要解决的问题是姓名与编号的对应关系，有两种方法:一是使用map<string, int>直接建立字符串与整型的映射关系;二是使用字符串hash的方法将字符串转换为整型。编号与姓名的对应关系则可以直接用string数组进行定义，或者使用map<int, string>也是可以的
根据题目中的要求，需要获得每个人的点权，即与之相关的通话记录的时长之和，而这显然可以在读入时就进行处理(假设 A与B 的通话时长为T那么A和B 的点权分别增加 T)。事实上，该步是在求与某个点相连的边的边权之和。
进行图的遍历。使用 DFS 遍历每个连通块，目的是获取每个连通块的头目(即连通块内点权最大的结点)、成员个数以及总边权
可以定义map<string, int>，来建立团伙头目的姓名与成员人数的映射关系。由于map中元素自动按键从小到大排序，因此自动满足了题目要求的“姓名字典序从小到大输出”的规定（map<typel, type2>是自动按键typel从小到大进行排序的）.
由于通话记录的条数最多有 1000 条，因此不同的人可能有 2000 人，所以数组大小必须在2000以上，否则会有一组数据“段错误”。

代码

#include <bits/stdc++.h>
using namespace std;
map<string, int> stringToInt;
map<int, string> intToString;
map<string, int> ans;
int idNumber = 1, k;

int stoifunc(string s) {
  if(stringToInt[s] == 0) {
    stringToInt[s] = idNumber;
    intToString[idNumber] = s;
    return idNumber++;
  } else {
    return stringToInt[s];
  }
}

int G[2010][2010], weight[2010];
bool vis[2010];

void dfs(int u, int &head, int &numMember, int &totalweight) {
  vis[u] = true;
  numMember++;
  if(weight[u] > weight[head])
    head = u;
  for(int v = 1; v < idNumber; v++) {
    if(G[u][v] > 0) {
      totalweight += G[u][v];
      // 防止有环
      G[u][v] = G[v][u] = 0;
      if(vis[v] == false)
        dfs(v, head, numMember, totalweight);
    }
  }
}

void dfsTrave() {
  for(int i = 1; i < idNumber; i++) {
    if(vis[i] == false) {
      int head = i, numMember = 0, totalweight = 0;
      dfs(i, head, numMember, totalweight);
      if(numMember > 2 && totalweight > k)
        ans[intToString[head]] = numMember;
    }
  }
}

int main() {
  int n, w;
  cin >> n >> k;
  string s1, s2;
  for(int i = 0; i < n; i++) {
    cin >> s1 >> s2 >> w;
    int id1 = stoifunc(s1);
    int id2 = stoifunc(s2);
    weight[id1] += w;
    weight[id2] += w;
    G[id1][id2] += w;
    G[id2][id1] += w;
  }
  dfsTrave();
  cout << ans.size() << endl;
  for(auto it = ans.begin(); it != ans.end(); it++)
    cout << it -> first << " " << it -> second << endl;
  return 0;
}

[1076] Forwards on Weibo

图的遍历，BFS

题目

在微博中，每个用户都可能被若干其他用户关注。而当该用户发布一条信息时，他的关注者就可以看到这条信息并选择是否转发它，且转发的信息也可以被转发者的关注者再次转发，但同一用户最多只转发该信息一次(信息的最初发布者不能转发该信息)。现在给出 N个用户的关注情况(即他们各自关注了哪些用户) 以及一个转发层数上限 L，并给出最初发布消息的用户编号，求在转发层数上限内消息最多会被多少用户转发。

分析与注意点

使用DFS遍历很容易出错，因为需要注意一种情况，即可能有一个用户X在第i次被访问，但是此时已经达到转发层数上限，故无法继续遍历。但若该用户可以通过另一条路径更快地被访问到，那么是可以继续深入遍历的。

代码

#include <bits/stdc++.h>
using namespace std;
int n, l;
vector<int> vis;
vector<vector<int>> G;

void dfs(int a, int depth, int &tot) {
  vis[a] = true;
  if (depth > l)  return;
  for (int i = 0; i < G[a].size(); i++) {
    int v = G[a][i];
    // cout << v << endl;
    if (vis[v] == false) {
      tot++;
      dfs(v, depth + 1, tot);
    }
  }
}

void bfs(int a, int &tot) {
  queue<int> q;
  q.push(a);
  vis[a] = true;
  int layer = -1;
  while (!q.empty()) {
    int num = q.size();
    layer++;
    if (layer > l)  return;
    for(int i = 0; i < num; i++) {
      int cur = q.front();
      q.pop();
      if (layer)  tot++;  // layer=0时访问的是发博的用户本身，不计入
      for (int j = 0; j < G[cur].size(); j++)
        if (vis[G[cur][j]] == false) {
          vis[G[cur][j]] = true;
          q.push(G[cur][j]);
        }
    }
  }
}

int main() {
  cin >> n >> l;
  int num, k;
  G.resize(n + 1);
  vis.resize(n + 1, false);
  for (int i = 1; i <= n; i++) {
    cin >> num;
    for (int j = 1; j <= num; j++) {
      cin >> k;
      G[k].push_back(i);
    }
  }
  cin >> num;
  for (int i = 0; i < num; i++) {
    fill(vis.begin(), vis.end(), false);
    cin >> k;
    int tot = 0;
    bfs(k, tot);
    cout << tot;
    if (i != num - 1)  cout << endl;
  }
  return 0;
}

单源最短路径

碰到有两条及以上可以达到最短距离的路径，题目就会给出一个第二标尺(第一标尺是距离)，要求在所有最短路径中选择第二标尺最优的一条路径。而第二标尺常见的是以下三种出题方法或其组合:

给每条边再增加一个边权（比如说花费），然后要求在最短路径有多条时要求路径上的花费之和最小（如果边权是其他含义，也可以是最大）。

给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大（如果点权是其他含义的话也可以是最小)。

直接问有多少条最短路径。

[1003] Emergency

点权

题目

给出N个城市，M条无向边。每个城市中都有一定数目的救援小组，所有边的边权已知。现在给出起点和终点，求从起点到终点的最短路径条数及最短路径上的救援小组数目之和。如果有多条最短路径，则输出数目之和最大的

分析与注意点

Dijkstra算法只能解决不存在负环的问题，使用邻接矩阵实现的dijkstra算法的复杂度是 $O(V^2)$，使用邻接表的话，更新最短距离只需要访问每条边一次即可，因此这部分的复杂度是 $O(E)$.但是每次要枚举所有的顶点来查找下一个使用的顶点，因此最终复杂度还是 $O(V^2)$。在 $|E|$ 比较小时，大部分的时间都花在了查找下一个使用的顶点上，因此需要使用合适的数据结构进行优化。
- 需要优化的是数值的插入（更新）和取出最小值两个操作，把每个顶点当前的最短距离用堆来维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要用的顶点。这样堆中的元素共有 $O(V)$ 个，更新和取出的操作有 $O(E)$ 次，因此整个算法的复杂度是 $O(ElogV)$。
- 若使用STL的priority_queue实现，在每次更新时往堆里插入当前最短距离和顶点的值对。插入的次数是 $O(E)$ 次，当取出的最小值不是最短距离的话，就丢弃这个值。这样整个算法也可以在同样的时间内完成。
BellmanFord算法中
- 用于解决单源最短路径存在负环的情况；
- 松弛操作不会超过 $V-1$ 次；
- 最短路径的求解方法、有多重标尺时的做法均与Dijkstra算法相同，唯一要注意的是统计最短路径条数的做法:由于 Bellman-Ford算法期间访问曾经访问过的顶点，如果单纯按照Diikstra算法中介绍的num数组的写法，将会反复累计已经计算过的顶点。为了解决这个问题，需要设置记录前驱的数组 set<int> pre[MAXV]，C++中是vector<set<int>> pre；当遇到一条和已有最短路径长度相同的路径时，必须重新计算最短路径条数。
- 由于算法需要遍历所有的边，因此用邻接表比较方便，且邻接矩阵会使得时间复杂度上升到 $O(V^3)$
SPFA算法就是优化后的BellmanFord算法。由于只有当某个顶点u的d[u]值改变时，从它出发的边的邻接点v的d[v]值才有可能被改变。由此可以进行一个优化：建立一个队列，每次将队首顶点u取出，然后对从u出发的所有边 u->v 进行松驰操作，也就是判断 d[u] + length[u->v] < d[v] 是否成立，如果成立，则用d[u]+length[u->v]覆盖d[v]，于是d[v]获得更优的值，此时如果v不在队列中，就把加入队列。这样操作直到队列为空（说明图中没有从源点可达的负环），或是某个顶点的入队次数超过 $V-1$
三种算法的时间复杂度
- Dijkstra算法：$O(V^2+E)$，进行堆优化后是 $O(VlogV+E)$；
- BellmanFord算法：$O(VE)$；
- SPFA：当不存在负环的时候是 $O(kE)$（一般$k$是一个不超过2的常数），经常会比堆优化后的Dijkstra还高效；但若存在负环则会退化成 $O(VE)$

代码

Dijkstra算法

int n, m, c1, c2;
vector<int> team, t, vis, d, num;
vector<vector<int>> G;

void Dijkstra(int s) {
  d[s] = 0;
  num[s] = 1;
  t[s] = team[s];
  for (int i = 0; i < n; i++) {
    int u = -1, mx = INT_MAX;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)  return;
    vis[u] = true;
    for (int v = 0; v < n; v++) {
      if (vis[v] == false && G[u][v] != INT_MAX) {
        if (d[u] + G[u][v] < d[v]) {
          d[v] = G[u][v] + d[u];
          num[v] = num[u];
          t[v] = t[u] + team[v];
        } else if (d[u] + G[u][v] == d[v]) {
          num[v] += num[u];
          t[v] = max(t[v], t[u] + team[v]);
        }
      }
    }
  }
  return;
}

int main() {
  cin >> n >> m >> c1 >> c2;
  t.resize(n, 0);
  num.resize(n, 0);
  d.resize(n, INT_MAX);
  vis.resize(n, false);
  G.resize(n, vector<int>(n, INT_MAX));
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    team.push_back(k);
  }
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    G[a][b] = w;
    G[b][a] = w;
  }
  Dijkstra(c1);
  cout << num[c2] << " " << t[c2];
  return 0;
}

堆优化版本Dijkstra模板

struct edge {int to,cost;};
typedef pair<int,int> P; //first是最短距离，second是顶点的编号
int V;//顶点个数
vector<edge> G[MAXV];
int d[MAXV];

void dijkstra(int s) {
  priority_queue<P,vector<P>,greater<P> > que;
  memset(d,INF,sizeof d);
  d[s] = 0;
  que.push(P(0,s)); //把起点推入队列
  while(!que.empty()) {
    P p = que.top(); que.pop();
    int v = p.second; //顶点的编号
    if (d[v] < p.first) continue;
    for(int i = 0; i < G[v].size(); i++) {
      edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to],e.to));
      }
    }
  }
}

BellmanFord算法

// BellmanFord + DFS
struct Node {
  int v;
  int dis;
  Node(int _v, int _dis): v(_v), dis(_dis) {}
};
int n, m, c1, c2;
vector<int> team, d, t, num;
vector<set<int>> pre;
vector<vector<Node>> Adj;

bool Bellman_Ford(int s) {
  d[s] = 0;
  for (int i = 0; i < n - 1; i++) {
    for (int u = 0; u < n; u++) {
      for (int k = 0; k < Adj[u].size(); k++) {
        if (d[u] == INT_MAX)  continue;
        int v = Adj[u][k].v;
        int dtc = Adj[u][k].dis;
        if (d[u] + dtc < d[v]) {
          d[v] = d[u] + dtc;
          pre[v].clear();
          pre[v].insert(u);
        } else if (d[u] + dtc == d[v]) {
          pre[v].insert(u);
        }
      }
    }
  }
  for (int u = 0; u < n; u++) {
    for (int k = 0; k < Adj[u].size(); k++) {
      int v = Adj[u][k].v;
      int dtc = Adj[u][k].dis;
      if (d[u] + dtc < d[v])
        return false;
    }
  }
  return true;
}

int maxSum = INT_MIN, cnt = 0;
vector<int> tempPath, ansPath;
void dfs(int v) {
  if (v == c1) {
    tempPath.push_back(v);
    int curSum = 0;
    for (int i = tempPath.size() - 1; i >= 0; i--) {
      curSum += team[tempPath[i]];
    }
    if (curSum > maxSum) {
      maxSum = curSum;
      ansPath = tempPath;
    }
    cnt++;
    tempPath.pop_back();
    return;
  }
  tempPath.push_back(v);
  set<int>::iterator it;
  for (it = pre[v].begin(); it != pre[v].end(); it++) {
    dfs(*it);
  }
  tempPath.pop_back();
  return;
}

int main() {
  cin >> n >> m >> c1 >> c2;
  // t.resize(n, 0);
  // num.resize(n, 0);
  d.resize(n, INT_MAX);
  pre.resize(n);
  Adj.resize(n);
  for (int i = 0; i < n; i++) {
    int cur;
    cin >> cur;
    team.push_back(cur);
  }
  for (int i = 0; i < m; i++) {
    int u, v, l;
    cin >> u >> v >> l;
    Adj[u].push_back(Node(v, l));
    Adj[v].push_back(Node(u, l));
  }
  bool flag = Bellman_Ford(c1);
  // bool flag = Single_Bellman_Ford(c1);
  if (!flag) {
    cout << "No Solution";
    return 0;
  }
  // cout << num[c2] << " " << t[c2];
  dfs(c2);
  cout << cnt << " " << maxSum;
  return 0;
}

// 不用dfs，直接在bellman里面求解第二标准
bool Single_Bellman_Ford(int s) {
  d[s] = 0;
  t[s] = team[s];
  num[s] = 1;
  for (int i = 0; i < n - 1; i++) {
    for (int u = 0; u < n; u++) {
      for(auto p: Adj[u]) {
        // INT_MAX一定要跳过，否则会发生正溢出
        // 不想写这个continue可以把d数组的最大值初始化为0x3fffffff
        if (d[u] == INT_MAX)
          continue;
        if(d[p.v] > d[u] + p.dis) {
          d[p.v] = d[u] + p.dis;
          num[p.v] = num[u];
          t[p.v] = t[u] + team[p.v];
          pre[p.v].clear();
          pre[p.v].insert(u);
        }
        else if(d[p.v] == d[u] + p.dis) {
          t[p.v] = max(t[u] + team[p.v], t[p.v]);
          pre[p.v].insert(u);
          num[p.v] = 0;
          for(auto k: pre[p.v])
            num[p.v] += num[k];
        }
      }
    }
  }
  for (int u = 0; u < n; u++) {
    for (auto p: Adj[u]) {
      if(d[p.v] > d[u] + p.dis)
        return false;
    }
  }
  return true;
}

SPFA算法

struct Node {
  int v;
  int w;
  Node(int _v, int _w): v(_v), w(_w) {}
};
const int MAX = 0x3fffffff;
vector<bool> inq;
vector<int> team, d, innum;
vector<set<int>> pre;
vector<vector<Node>> Adj;
int n, m, c1, c2;

bool SPFA(int s) {
  d.resize(n, MAX);
  inq.resize(n, false);
  innum.resize(n, 0);
  d[s] = 0;
  queue<int> q;
  q.push(s);
  inq[s] = true;
  innum[s]++;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (auto p: Adj[u]) {
      if (d[u] + p.w < d[p.v]) {
        d[p.v] = d[u] + p.w;
        pre[p.v].clear();
        pre[p.v].insert(u);
        if (!inq[p.v]) {
          q.push(p.v);
          inq[p.v] = true;
          innum[p.v]++;
          if (innum[p.v] >= n)
            return false;
        }
      } else if (d[u] + p.w == d[p.v]) {
        pre[p.v].insert(u);
      }
    }
  }
  return true;
}

int cnt = 0, maxSum = INT_MIN;
vector<int> tempPath, ansPath;
void dfs(int v) {
  if (v == c1) {
    tempPath.push_back(v);
    int curSum = 0;
    for (int i = tempPath.size() - 1; i >= 0; i--)
      curSum += team[tempPath[i]];
    if (curSum > maxSum) {
      maxSum = curSum;
      ansPath = tempPath;
    }
    cnt++;
    tempPath.pop_back();
    return;
  }
  tempPath.push_back(v);
  for (auto p: pre[v])
    dfs(p);
  tempPath.pop_back();
  return;
}

int main() {
  cin >> n >> m >> c1 >> c2;
  pre.resize(n);
  team.resize(n);
  Adj.resize(n);
  for (int i = 0; i < n; i++)
    cin >> team[i];
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    Adj[u].push_back(Node(v, w));
    Adj[v].push_back(Node(u, w));
  }
  bool flag = SPFA(c1);
  if (!flag)  cout << "No Solution!";
  else {
    dfs(c2);
    cout << cnt << " " << maxSum;
  }
  return 0;
}

[1018] Public Bike Management

点权

题目

城市里有一些公共自行车站，每个车站的自行车最大容量为一个偶数 Cmax，且如果一个车站中自行车的数量恰好为 Cmax/2，那么称该车站处于“完美状态”。而如果一个车站容量是满的或是空的，那么控制中心(PBMC)就会携带或从路上收集一定数量的自行车前往该车站，以使问题车站及沿途所有车站都达到“完美状态”。现在给出Cmax、车站数目N(不含控制中心PBMC)问题车站编号 Sp、无向边数M及边权，求一条从PBMC(记为0号)到达问题车站Sp的最短路径，输出需要从 PBMC 携带的自行车数目、最短路径、到达问题车站后需要带回的自行车数目。如果最短路径有多条，那么选择从PBMC携带的自行车数目最少的;如果仍然有多条，那么选择最后从问题车站带回的自行车数目最少的。注意:沿途所有车站的调整过程必须在前往问题车站的过程中就调整完毕，带回时不再调整。

分析与注意点

把每个点的点权 (自行车数目)都减去 Cmax/2，这样就可以用点权的正负来直接判断当前车站是需要补给还是需要带走额外的车辆。
由于需要输出应从PBMC携带的自行车数目与从问题车站带回的自行车数目，因此对每个顶点来说需要增加两个属性：从PBMC到当前车站必须携带的自行车数目Need以及到达当前车站时手上多余的自行车数目Remain。
- 如果当前车站u的点权weight[u]为正，说明需要从该车站额外带走自行车，因此新的 Remain 等于旧的 Remain 加上weight[u];
- 而如果当前车站的点权weight[u]为负，说明当前车站需要补给自行车的数量为abs(weight[u])，此时如果Remain大于0，就可以用来补给当前车站，但如果 Remain 不够完全补给，剩余部分需要从PBMC携带，故Need增加这个数值。

代码

Dijkstra算法

int cmax, n, sp, m;
int minNeed = INT_MAX, minRemain = INT_MAX;
vector<vector<int>> G, pre;
vector<int> bike, d, vis, path, tempPath;

void Dijkstra(int s) {
  d[s] = 0;
  for (int i = 0; i <= n; i++) {
    int u = -1, mx = INT_MAX;
    for (int j = 0; j <= n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)  return;
    vis[u] = true;
    for (int v = 0; v <= n; v++) {
      if (vis[v] == false && G[u][v] != INT_MAX) {
        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);
        }
      }
    }
  }
  return;
}

void dfs(int v) {
  if (v == 0) {
    tempPath.push_back(v);
    int need = 0, remain = 0;
    for (int i = tempPath.size() - 1; i >= 0; i--) {
      int cur = tempPath[i];
      if (bike[cur] > 0) {
        remain += bike[cur];
      } else {
        if (remain > abs(bike[cur]))
          remain -= abs(bike[cur]);
        else {
          need += abs(bike[cur]) - remain;
          remain = 0;
        }
      }
    }
    if (need < minNeed || (need == minNeed && remain < minRemain)) {
      minNeed = need;
      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();
  return;
}

int main() {
  cin >> cmax >> n >> sp >> m;
  pre.resize(n + 1);
  d.resize(n + 1, INT_MAX);
  bike.resize(n + 1, 0);
  vis.resize(n + 1, false);
  G.resize(n + 1, vector<int>(n + 1, INT_MAX));
  for (int i = 1; i <= n; i++) {
    cin >> bike[i];
    bike[i] -= cmax / 2;
  }
  for (int i = 0; i < m; i++) {
    int a, b, t;
    cin >> a >> b >> t;
    G[a][b] = t;
    G[b][a] = t;
  }
  Dijkstra(0);
  dfs(sp);
  cout << minNeed << " ";
  for (int i = path.size() - 1; i >= 0; i--) {
    cout << path[i];
    if (i > 0)  cout << "->";
  }
  cout << " " << minRemain;
  return 0;
}

SPFA算法

struct Node {
  int v;
  int w;
  Node(int _v, int _w): v(_v), w(_w) {}
};

const int MAX = 0x3fffffff;
int cmax, n, sp, m;
vector<bool> inq;
vector<int> bike, d;
vector<set<int>> pre;
vector<vector<Node>> Adj;

// 已知不存在负环可以去掉记录入队次数的num数组
void SPFA(int s) {
  inq.resize(n + 1, false);
  d.resize(n + 1, MAX);
  queue<int> q;
  q.push(s);
  inq[s] = true;
  d[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (auto p: Adj[u]) {
      if (d[u] + p.w < d[p.v]) {
        d[p.v] = d[u] + p.w;
        pre[p.v].clear();
        pre[p.v].insert(u);
        if (!inq[p.v]) {
          q.push(p.v);
          inq[p.v] = true;
        }
      } else if (d[u] + p.w == d[p.v]) {
        pre[p.v].insert(u);
      }
    }
  }
  return;
}

int ansNeed = INT_MAX, ansRemain = INT_MAX;
vector<int> tempPath, ansPath;
void dfs(int v) {
  tempPath.push_back(v);
  if (v == 0) {
    int remain = 0, need = 00;
    for (int i = tempPath.size() - 1; i >= 0; i--) {
      int u = tempPath[i];
      if (bike[u] > 0) {
        remain += bike[u];
      } else {
        if (remain > abs(bike[u]))
          remain -= abs(bike[u]);
        else {
          need += abs(bike[u]) - remain;
          remain = 0;
        }
      }
    }
    if (need < ansNeed || (need == ansNeed && remain < ansRemain)) {
      ansNeed = need;
      ansRemain = remain;
      ansPath = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  for (auto p: pre[v])
    dfs(p);
  tempPath.pop_back();
  return;
}

int main() {
  cin >> cmax >> n >> sp >> m;
  Adj.resize(n + 1);
  pre.resize(n + 1);
  bike.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> bike[i];
    bike[i] -= cmax / 2;
  }
  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    Adj[u].push_back(Node(v, w));
    Adj[v].push_back(Node(u, w));
  }
  SPFA(0);
  dfs(sp);
  cout << ansNeed << " ";
  for (int i = ansPath.size() - 1; i >= 0; i--) {
    cout << ansPath[i];
    if (i)  cout << "->";
  }
  cout << " " << ansRemain;
  return 0;
}

[1030] Travel Plan

边权

题目

有N个城市(编号为0~N-1)M条道路(无向边，并给出M条道路的距离属性与花费属性。现在给定起点 S 与终点 D，求从起点到终点的最短路径、最短距离及花费。注意:如果有多条最短路径，则选择花费最小的那条。

分析与注意点

SPFA算法中，前驱结点的保存时采用了pair数据结构来同时保存边权，在数据量大（最后一个测试点）时，使用邻接表空间消耗大概是邻接矩阵的一半

代码

Dijkstra算法

int n, m, e, s, minCost = INT_MAX;
vector<int> d, vis, tempPath, path;
vector<vector<int>> pre;

struct Node {
  int w;
  int c;
  Node(int _w, int _c): w(_w), c(_c) {}
};
vector<vector<Node>> G;

void Dijkstra(int s) {
  d[s] = 0;
  for (int i = 0; i < n; i++) {
    int u = -1, mx = INT_MAX;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)  return;
    vis[u] = true;
    for (int v = 0; v < n; v++) {
      if (vis[v] == false && G[u][v].w != INT_MAX) {
        if (d[u] + G[u][v].w < d[v]) {
          d[v] = d[u] + G[u][v].w;
          pre[v].clear();
          pre[v].push_back(u);
        } else if (d[u] + G[u][v].w == d[v]) {
          pre[v].push_back(u);
        }
      }
    }
  }
  return;
}

void dfs(int v) {
  if (v == s) {
    tempPath.push_back(v);
    int cost = 0;
    for (int i = tempPath.size() - 1; i > 0; i--) {
      int id = tempPath[i], nxt = tempPath[i-1];
      cost += G[id][nxt].c;
    }
    // printf("cost %d %d\n", cost, minCost);
    if (cost < minCost) {
      minCost = cost;
      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();
  return;
}

int main() {
  cin >> n >> m >> s >> e;
  pre.resize(n);
  d.resize(n, INT_MAX);
  vis.resize(n, false);
  G.resize(n, vector<Node>(n, Node(INT_MAX, INT_MAX)));
  for (int i = 0; i < m; i++) {
    int u, v, dtc, cst;
    cin >> u >> v >> dtc >> cst;
    G[u][v] = Node(dtc, cst);
    G[v][u] = Node(dtc, cst);
  }
  Dijkstra(s);
  dfs(e);
  for (int i = path.size() - 1; i >= 0; i--)
    cout << path[i] << " ";
  printf("%d %d", d[e], minCost);
  return 0;
}

SPFA算法

struct Node {
  int v, w, c;
  Node(int _v, int _w, int _c): v(_v), w(_w), c(_c) {}
};

int n, m, st, ed;
vector<bool> inq;
vector<int> d;
vector<set<pair<int, int>>> pre;
vector<vector<Node>> Adj;
const int MAX = 0x3fffffff;

void SPFA(int s) {
  d.resize(n, MAX);
  inq.resize(n, false);
  queue<int> q;
  q.push(s);
  inq[s] = true;
  d[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = false;
    for (auto p: Adj[u]) {
      if (d[u] + p.w < d[p.v]) {
        d[p.v] = d[u] + p.w;
        pre[p.v].clear();
        pre[p.v].insert(make_pair(u, p.c));
        if (!inq[p.v]) {
          q.push(p.v);
          inq[p.v] = true;
        }
      } else if (d[u] + p.w == d[p.v]) {
        pre[p.v].insert(make_pair(u, p.c));
      }
    }
  }
  return;
}

int ansCost = INT_MAX;
vector<pair<int, int>> tempPath, ansPath;
void dfs(pair<int, int> v) {
  tempPath.push_back(v);
  if (v.first == st) {
    int cost = 0;
    // 注意这里是从起始点（最后一个元素）到倒二个元素，计算边权
    for (int i = tempPath.size() - 1; i > 0; i--) {
      cost += tempPath[i].second;
    }
    if (cost < ansCost) {
      ansCost = cost;
      ansPath = tempPath;
    }
    tempPath.pop_back();
    return;
  }
  for (auto p: pre[v.first])
    dfs(p);
  tempPath.pop_back();
  return;
}

int main() {
  cin >> n >> m >> st >> ed;
  pre.resize(n);
  Adj.resize(n);
  for (int i = 0; i < m; i++) {
    int u, v, w, c;
    cin >> u >> v >> w >> c;
    Adj[u].push_back(Node(v, w, c));
    Adj[v].push_back(Node(u, w, c));
  }
  SPFA(st);
  dfs(make_pair(ed, 0));
  for (int i = ansPath.size() - 1; i >= 0; i--)
    cout << ansPath[i].first << " ";
  printf("%d %d", d[ed], ansCost);
  return 0;
}

Next Post

PAT甲级2016春真题
Previous Post

Z-Order

CATALOG