文章

kuangbin专题4：最短路练习

发表于 更新于
作者 BlankR 7 分钟阅读

配合oi-wiki的最短路章节狠狠复习了。

知识点

单源最短路

SPFA

  • Bellman-Ford的一种优化，适用于中/小图
  • 时间复杂度\(O(NM)\) 
    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

    bool spfa(int s)
{
  memset(vis, 0, sizeof(vis));
  memset(cnt, 0, sizeof(cnt));
  memset(dis, INF, sizeof(dis));

  queue<int> q;
  dis[s] = 0, vis[s] = 1, cnt[s] = 1;
  q.push(s);
  while (!q.empty())
  {
      int u = q.front();
      q.pop();
      vis[u] = 0;
      for (int i = head[u]; ~i; i = e[i].next)
      {
          int v = e[i].v;
          int c = e[i].c;
          if (dis[v] > dis[u] + c)
          {
              dis[v] = dis[u] + c;
              if (!vis[v])
              {
                  q.push(v), vis[v] = 1;
                  if (++cnt[v] > n)
                      return false;
              }
          }
      }
  }
  return true;
}

Dijkstra

  • 适用于大/中图
  • 不能检测负环
  • 用priority_queue优化后时间复杂度\(O(MlogM)\) 
    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

    void dijkstra(int s)
{
  priority_queue<PII, vector<PII>, greater<PII> > q;
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  q.push(make_pair(0, s));
  dis[s] = 0;
  while (!q.empty())
  {
      int u = q.top().second;
      q.pop();
      if (vis[u])
          continue;
      vis[u] = 1;
      for (int i = head[u]; ~i; i = edge[i].next)
      {
          int v = edge[i].v;
          int c = edge[i].c;
          if (dis[v] > dis[u] + c)
          {
              dis[v] = dis[u] + c;
              q.push(make_pair(dis[v], v));
          }
      }
  }
}

每对点之间的最短路

Floyd

  • 适用于小图
  • 时间复杂度\(O(n^3)\)，空间复杂度\(O(n^2)\) 
    1
2
3
4
5
6
7
8
9

    void floyd()
{
  for (int k = 0; k < n; k++)
      for (int x = 0; x < n; x++)
          for (int y = 0; y < n; y++)
          {
              f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
          }
}

Johnson

  • 适用于大/中图
  • 时间复杂度\(O(NMlogM)\)

链式前向星

  • 名字起得很fancy，但本质就是链表存图
  • 比邻接矩阵效率高，比邻接表好写
  • 时间复杂度、空间复杂度均为\(O(n)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

struct E
{
    int v, c, next;
} edge[MAXM];
int len;
int head[MAXN];
void add(int u, int v, int c)
{
    edge[len].v = v;
    edge[len].c = c;
    edge[len].next = head[u];
    head[u] = len++;
}

void init()
{
    memset(head, -1, sizeof(head));
    memset(edge, 0, sizeof(edge));
    len = 0;
}

// traverse
for (int i = head[u]; ~i; i = edge[i].next) {}

应用：

差分约束问题

定义

  • 差分约束系统包含\(n\)个变量\(x_1,x_2,...,x_n\)以及\(m\)个约束条件
  • 每个约束条件形如\(x_i-x_j\leq c_k\)，其中\(c_k\)是一个常数
  • 问题为：求一组解，使得所有约束条件得到满足；或者判断无解

    思路

  • 将约束条件变形为\(x_i\leq x_j+c_k\)后发现与单源最短路中的三角形不等式\(dis[y]\leq dis[x]+z\)形似
  • 因此，我们可以通过将每个\(x_i\)视为一个节点，对于每个约束条件\(x_i-x_j\leq c_k\)，建立一条\(j\rightarrow i\)的权值为\(c_k\)的有向边，将差分约束转换为单源最短路问题
  • 做法：设一个超级源点0，从0向每一个点连一条权重为0的边，然后跑单源最短路算法（用SPFA或在有解的前提下用djkstra）。若图中存在负环，则给定的差分约束系统无解；否则\(x_i=dis[i]\)为一组解

    应用

  • 求两个变量差的最大值：不等式化为\(\leq\)形式，然后求最短路
  • 求两个变量差的最小值：不等式化为\(\geq\)形式，然后求最长路

    例题

  • POJ - 3159、POJ - 3169

检测正/负环

  • SPFA
  • 例题：POJ1860、POJ3259、POJ2240、LightOJ - 1074

题目记录：

  1. POJ - 2387：单源最短路模版题
  2. POJ - 2253：求最大权值最小的路；单源最短路变形，或者最小生成树prim/kruskal
  3. POJ - 1797：求最小权值最大的路；单源最短路变形，或最大生成树（最小生成树变形）
  4. POJ - 3268：正反单源最短路
  5. POJ - 1860：SPFA检测正环
  6. POJ - 3259：SPFA检测负环
  7. POJ - 1502：单源最短路模版题
  8. POJ - 3660：floyd判断是否与每一个其它点都有边
  9. POJ - 2240：多次SPFA检测正环，好像也可以用floyd
  10. POJ - 1551：链式向前星+优化的正反单源最短路，非常容易TLE！！！！不要用vector不然会死很惨
  11. POJ - 3159：差分约束系统+优化的正反单源最短路
  12. POJ - 2502：单源最短路模版题，建图是难点
  13. POJ - 1062：多次单源最短路，枚举等级范围
  14. POJ - 1847: 单源最短路模版题，每个switch的第一条路边权为0，其它为1
  15. LightOJ - 1074：单源最短路，但是有负环，SPFA+dfs标记负环所在的联通块并视为无法到达
  16. HDU - 4725：单源最短路，每层建立一个超级结点并向每个该层的结点连一条单向边。每层的所有结点再向上下层的超级结点连单向边。注意MAXN开两倍。
  17. HDU - 3416（网络流，先跳过）
  18. HDU - 4370：矩阵转换成图，\(X_{ij}\)视为从结点\(i\)到\(j\)是否存在边，\(C_{ij}\)视为从结点\(i\)到\(j\)的边的权值（如果存在的话）。题目条件转换为点1出度为1，点n入度为1。注意，题目中没有规定点1的入度和点n的出度，也就是说可以存在环（非自环）。除了非环路径以外，还要判断起点和终点各一个自环的情况。
  19. POJ - 3169：差分约束系统，规定差值上限时权值为正，规定下限时为负

注意事项

  • 多个测试用例清空图
  • 0-index的时候别忘了处理输入
  • 边数组开大点
algorithm, kuangbin
djkstra spfa floyd
本文由作者按照 CC BY 4.0 进行授权