Skip to content

Minimum Cycle

Introduction

Problem

Given a graph, find the cycle with \(n\) nodes that has the minimum sum of edge weights \((n\ge 3)\).

The minimum cycle in a graph is also known as the girth.

Process

Brute Force Solution

Let there be an edge between \(u\) and \(v\) with weight \(w\), and let \(dis(u,v)\) denote the shortest path between \(u\) and \(v\) after removing the edge between \(u\) and \(v\).

Then the minimum cycle in an undirected graph is \(dis(u,v)+w\).

Note that if finding the minimum cycle in a directed graph, the corresponding formula should be modified: the minimum cycle is \(dis(v,u)+w\).

Total time complexity: \(O(n^2m)\).

Dijkstra

Related link: Shortest Path/Dijkstra

Process

Enumerate all edges. For each edge, run Dijkstra from the starting point of that edge after deleting it, following the same principle as above.

Properties

Time complexity: \(O(m(n+m)\log n)\).

Floyd

Related link: Shortest Path/Floyd

Process

Let \(val\left(u,v\right)\) denote the edge weight between \(u\) and \(v\) in the original graph.

We note a property of the Floyd algorithm: when the outermost loop reaches point \(k\) (before starting the \(k\)-th iteration), the shortest path array \(dis\) satisfies that \(dis_{u,v}\) represents the shortest path from \(u\) to \(v\) using only points with indices in \(\left[1, k\right)\).

By the definition of a minimum cycle, it has at least three vertices. Let \(w\) be the vertex with the largest index in the cycle, and let \(u\) and \(v\) be the two points adjacent to \(w\) on the cycle. Then when the outermost loop enumerates \(k=w\), the length of the cycle is \(dis_{u,v}+val\left(v,w\right)+val\left(w,u\right)\).

Therefore, during the loop, for each \(k\), enumerate \((i,j)\) satisfying \(i<k,j<k\) and update the answer.

Recording the Path

Now we know the cycle is of the form \(u\to k\to v\), and then from \(v\) back to \(u\) (all points visited have indices \(<k\)).

The problem reduces to finding the path \(v\leadsto u\). By the triangle inequality \(dis_{u,v}\le dis_{u,i}+dis_{i,v}\), consider recording \(pos_{u,v}=j\) as the point such that \(dis_{u,v}=dis_{u,j}+dis_{j,v}\). Clearly, \(j\) lies on the path \(v\leadsto u\).

Thus, the path can be split into two segments: \(v\leadsto j\) and \(j\leadsto u\), which can be handled recursively.

Proof that recursion does not fall into an infinite loop

Proof by contradiction.

Assume the cycle passes through a point \(u\) repeatedly. Then there must be an edge starting from \(u\) that, after traversing several edges, returns to \(u\). This forms a new cycle.

Since the graph contains no negative cycles (if there were a negative cycle, there would be no minimum cycle), the sum of edge weights of the new cycle must be less than or equal to that of the original cycle.

Therefore, we can simply take this new cycle, which does not pass through \(u\) repeatedly. The assumption is false, so the cycle does not pass through any point repeatedly.

Thus, when recursively processing points \(u\) and \(v\), their \(pos_{u,v}\) must not equal the indices of the two points, meaning a new point is added.

In particular, when \(u\) and \(v\) are adjacent, return directly.

Since the total number of points is \(n\), the number of additions (i.e., recursive calls) does not exceed \(n\), so recursion will not fall into an infinite loop.

Properties

Time complexity: \(O(n^3)\).

Implementation

Below are C++ and Python reference implementations (with path recording):

 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
// The graph has n nodes
int val[MAXN + 1][MAXN + 1];  // Adjacency matrix of the original graph
int cnt, path[MAXN + 5];      // Record the path and length of the minimum cycle

void get_path(int u, int v) {  // Get the path between u and v
  if (pos[u][v] == 0) return;

  int k = pos[u][v];
  get_path(u, k);
  path[++cnt] = k;
  get_path(k, v);
}

void Floyd(const int &n) {
  static int dis[MAXN + 1][MAXN + 1];  // Shortest path matrix
  static int pos[MAXN + 1][MAXN + 1];
  memcpy(dis, val, sizeof(val));
  memset(pos, 0, sizeof(pos));
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        if (ans >
            (long long)val[i][k] + val[k][j] + dis[i][j]) {  // Found a shorter cycle
          // Since j<i<k is guaranteed here, the three points are distinct, avoiding zero-length cycles.
          ans = val[i][k] + val[k][j] + dis[i][j], cnt = 0;
          path[++cnt] = i, path[++cnt] = k,
          path[++cnt] = j;  // Add i, k, j in order
          get_path(j, i);   // Add the path from j to i
        }

    for (int i = 1; i <= n; ++i)  // Normal Floyd update for shortest paths
      for (int j = 1; j <= n; ++j) {
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          dis[i][j] = dis[i][k] + dis[k][j];
          pos[i][j] = k;  // The current path can be updated via k
        }
      }
  }
}

  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
# Define a sufficiently large value to represent infinity
INF = sys.maxsize


def get_path(i, j, pos, path, cnt):
    """
    Recursively get the intermediate nodes on the shortest path from node i to node j.

    Args:
        i (int): Starting node (0-based index).
        j (int): Ending node (0-based index).
        pos (list[list[int]]): Matrix recording intermediate nodes on shortest paths. pos[i][j] = k means the shortest path from i to j passes through k.
        path (list[int]): List storing path nodes (using 0-based index).
        cnt (int): Current number of path nodes.

    Returns:
        int: Updated number of path nodes.
    """
    # If pos[i][j] is -1, there is no intermediate node between i and j
    if pos[i][j] == -1:
        return cnt

    # Get intermediate node k
    k = pos[i][j]
    # Recursively get the path from i to k
    cnt = get_path(i, k, pos, path, cnt)
    # Add intermediate node k to the path
    path[cnt] = k
    cnt += 1
    # Recursively get the path from k to j
    cnt = get_path(k, j, pos, path, cnt)
    return cnt


def find_minimum_cycle_undirected(n, edges):
    """
    Find the minimum cycle in an undirected graph using the Floyd-Warshall algorithm.

    Args:
        n (int): Number of nodes in the graph (1 to n).
        edges (list[tuple]): List of edges, each element is (u, v, w), indicating an edge between nodes u and v with weight w.
                             Node indices are 1 to n.

    Returns:
        tuple: Contains the length of the minimum cycle and the path.
               If no cycle exists, return (INF, []).
               The path is a list of node indices (1-based index).
    """
    # Use 0-based indexing internally
    N = n
    # Initialize adjacency matrix g, representing original edge weights
    g = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize shortest path matrix dis, initially same as g
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize pos matrix to record intermediate nodes on shortest paths
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # Set diagonal to 0 (distance from a node to itself)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # Build adjacency matrix from input edges (undirected graph)
    for u, v, w in edges:
        # Convert 1-based indices to 0-based
        u -= 1
        v -= 1
        # For undirected graph, edges are bidirectional
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # Initialize minimum cycle length to infinity
    min_cycle_len = INF
    # Initialize minimum cycle path
    min_cycle_path = []

    # Core part of Floyd-Warshall algorithm
    # k as intermediate node (0-based index)
    for k in range(N):
        # Before updating dis[i][j], check if a smaller cycle can be formed via node k
        # The cycle consists of i -> k -> j -> ... -> i
        # Here dis[i][j] is the shortest path considering nodes 0 to k-1 as intermediate nodes
        # The C++ code uses loops with i < k and j < i; we follow the same logic here (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # Check if i, k, j form a cycle connected via dis[i][j]
                # Ensure original edges g[i][k] and g[k][j] exist (not INF)
                # and the shortest path dis[i][j] from i to j exists (not INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # Reconstruct the path
                        path = [0] * (N + 5)  # Temporary array to store the path, large enough
                        cnt = 0
                        # Add i, k, j in order
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # Get intermediate nodes on the shortest path from j to i (using previously computed dis and pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # Extract actual path nodes (remove unused parts)
                        # Convert 0-based indices to 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # Standard Floyd-Warshall update for shortest paths
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # Record that the shortest path from i to j passes through k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path

Template Problem

AcWing 344 Sightseeing Tour

Given an undirected graph with \(n\) points, find a cycle containing at least \(3\) points, where the nodes on the cycle are distinct, and the sum of the lengths of the edges on the cycle is minimized.

This problem is known as the minimum cycle problem in undirected graphs.

You need to output the scheme of the minimum cycle. If the minimum cycle is not unique, output any one.

\(n \le 100\)

The time complexity of \(O(n^3)\) is acceptable. Apply the Floyd algorithm for finding the minimum cycle.

  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
#include <bits/stdc++.h>
using lint = long long;
// Define a sufficiently large constant for the maximum number of nodes in the graph
const int MAXN = 110;

// Define a sufficiently large value to represent infinity, initialize minimum cycle length
lint ans = 1e9;  // lint is an alias for long long

// Number of nodes n, number of edges m
// cnt records the number of nodes in the minimum cycle path
// path stores the nodes of the minimum cycle path
int n, m, cnt, path[MAXN];

// g stores the original graph's adjacency matrix
// dis stores the shortest path matrix (updated during Floyd-Warshall algorithm)
// pos records intermediate nodes on shortest paths, pos[i][j] = k means the shortest path from i to j passes through k
int g[MAXN][MAXN], dis[MAXN][MAXN], pos[MAXN][MAXN];

// Recursive function: get intermediate nodes on the shortest path from node u to node v
// Reconstruct the path based on the pos matrix
void get_path(int u, int v) {
  // If pos[u][v] is 0, there is no intermediate node between u and v, return directly
  if (pos[u][v] == 0) return;

  // Get intermediate node k
  int k = pos[u][v];
  // Recursively get the path from u to k
  get_path(u, k);
  // Add intermediate node k to the path
  path[++cnt] = k;
  // Recursively get the path from k to v
  get_path(k, v);
}

// Floyd-Warshall algorithm function: find the minimum cycle in the graph
void Floyd() {
  // Outer loop: k as intermediate node (1 to n)
  for (int k = 1; k <= n; ++k) {
    // Inner loops: i and j, used to check if a smaller cycle can be formed via node k
    // Loop order: i from 1 to k-1, j from 1 to i-1
    // This checks cycles of the form i -> k -> j -> ... -> i
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        // Check if connecting i and j via node k forms a smaller cycle
        // Cycle length is original edge weight g[i][k] + original edge weight g[k][j]
        // + current shortest path dis[i][j]
        if (ans > (long long)g[i][k] + g[k][j] + dis[i][j]) {
          // Found a smaller cycle
          ans = g[i][k] + g[k][j] + dis[i][j];  // Update minimum cycle length
          cnt = 0;                              // Reset path count
          // Add i, k, j to the path in order
          path[++cnt] = i, path[++cnt] = k, path[++cnt] = j;
          // Get intermediate nodes on the shortest path from j to i, add to path
          get_path(j, i);
        }

    // Standard Floyd-Warshall update for shortest paths
    // i from 1 to n, j from 1 to n
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j) {
        // If a shorter path from i to j can be obtained via intermediate node k
        if (dis[i][j] > dis[i][k] + dis[k][j]) {
          // Update shortest path
          dis[i][j] = dis[i][k] + dis[k][j];
          // Record that the shortest path from i to j passes through k
          pos[i][j] = k;
        }
      }
  }
}

// Main function
int main() {
  // Read number of nodes n and number of edges m
  std::cin >> n >> m;
  // Initialize original adjacency matrix g, set all edge weights to infinity (0x3f usually represents a large value)
  memset(g, 0x3f, sizeof(g));
  // Set distance from a node to itself to 0
  for (int i = 1; i <= n; ++i) g[i][i] = 0;
  // Read m edges, build original adjacency matrix g
  // For undirected graph, edges are bidirectional, take the smaller weight
  for (int i = 0, u, v, w; i < m; ++i) {
    std::cin >> u >> v >> w;
    g[u][v] = g[v][u] = std::min(g[u][v], w);
  }
  // Copy original adjacency matrix g to shortest path matrix dis
  memcpy(dis, g, sizeof(g));
  // Call Floyd algorithm to find minimum cycle
  Floyd();
  // Determine if a cycle exists based on minimum cycle length
  if (ans == 1e9) {  // If minimum cycle length is still infinity, no cycle exists
    puts("No solution.");
  } else {
    // If a cycle exists, print the path nodes
    // std::cout << "ans = " << ans << std::endl; // Print minimum cycle length (commented out)
    // Print path nodes, separated by spaces
    for (int i = 1; i <= cnt; ++i)
      std::cout << path[i]
                << (i == cnt ? "" : " ");  // No space after the last node
    std::cout << std::endl;                // Newline after printing the path
  }
  return 0;
}

  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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import copy
import sys

# Define a sufficiently large value to represent infinity
INF = sys.maxsize


def get_path(i, j, pos, path, cnt):
    """
    Recursively get the intermediate nodes on the shortest path from node i to node j.

    Args:
        i (int): Starting node (0-based index).
        j (int): Ending node (0-based index).
        pos (list[list[int]]): Matrix recording intermediate nodes on shortest paths. pos[i][j] = k means the shortest path from i to j passes through k.
        path (list[int]): List storing path nodes (using 0-based index).
        cnt (int): Current number of path nodes.

    Returns:
        int: Updated number of path nodes.
    """
    # If pos[i][j] is -1, there is no intermediate node between i and j
    if pos[i][j] == -1:
        return cnt

    # Get intermediate node k
    k = pos[i][j]
    # Recursively get the path from i to k
    cnt = get_path(i, k, pos, path, cnt)
    # Add intermediate node k to the path
    path[cnt] = k
    cnt += 1
    # Recursively get the path from k to j
    cnt = get_path(k, j, pos, path, cnt)
    return cnt


def find_minimum_cycle_undirected(n, edges):
    """
    Find the minimum cycle in an undirected graph using the Floyd-Warshall algorithm.

    Args:
        n (int): Number of nodes in the graph (1 to n).
        edges (list[tuple]): List of edges, each element is (u, v, w), indicating an edge between nodes u and v with weight w.
                             Node indices are 1 to n.

    Returns:
        tuple: Contains the length of the minimum cycle and the path.
               If no cycle exists, return (INF, []).
               The path is a list of node indices (1-based index).
    """
    # Use 0-based indexing internally
    N = n
    # Initialize adjacency matrix g, representing original edge weights
    g = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize shortest path matrix dis, initially same as g
    dis = [[INF for _ in range(N)] for _ in range(N)]
    # Initialize pos matrix to record intermediate nodes on shortest paths
    pos = [[-1 for _ in range(N)] for _ in range(N)]

    # Set diagonal to 0 (distance from a node to itself)
    for i in range(N):
        g[i][i] = 0
        dis[i][i] = 0

    # Build adjacency matrix from input edges (undirected graph)
    for u, v, w in edges:
        # Convert 1-based indices to 0-based
        u -= 1
        v -= 1
        # For undirected graph, edges are bidirectional
        g[u][v] = min(g[u][v], w)
        g[v][u] = min(g[v][u], w)
        dis[u][v] = min(dis[u][v], w)
        dis[v][u] = min(dis[v][u], w)

    # Initialize minimum cycle length to infinity
    min_cycle_len = INF
    # Initialize minimum cycle path
    min_cycle_path = []

    # Core part of Floyd-Warshall algorithm
    # k as intermediate node (0-based index)
    for k in range(N):
        # Before updating dis[i][j], check if a smaller cycle can be formed via node k
        # The cycle consists of i -> k -> j -> ... -> i
        # Here dis[i][j] is the shortest path considering nodes 0 to k-1 as intermediate nodes
        # The C++ code uses loops with i < k and j < i; we follow the same logic here (0-based)
        for i in range(k):  # 0 <= i < k
            for j in range(i):  # 0 <= j < i
                # Check if i, k, j form a cycle connected via dis[i][j]
                # Ensure original edges g[i][k] and g[k][j] exist (not INF)
                # and the shortest path dis[i][j] from i to j exists (not INF)
                if g[i][k] != INF and g[k][j] != INF and dis[i][j] != INF:
                    current_cycle_len = g[i][k] + g[k][j] + dis[i][j]
                    if current_cycle_len < min_cycle_len:
                        min_cycle_len = current_cycle_len
                        # Reconstruct the path
                        path = [0] * (N + 5)  # Temporary array to store the path, large enough
                        cnt = 0
                        # Add i, k, j in order
                        path[cnt] = i
                        cnt += 1
                        path[cnt] = k
                        cnt += 1
                        path[cnt] = j
                        cnt += 1
                        # Get intermediate nodes on the shortest path from j to i (using previously computed dis and pos)
                        cnt = get_path(j, i, pos, path, cnt)
                        # Extract actual path nodes (remove unused parts)
                        # Convert 0-based indices to 1-based
                        min_cycle_path = [node + 1 for node in path[:cnt]]

        # Standard Floyd-Warshall update for shortest paths
        for i in range(N):
            for j in range(N):
                if (
                    dis[i][k] != INF
                    and dis[k][j] != INF
                    and dis[i][j] > dis[i][k] + dis[k][j]
                ):
                    dis[i][j] = dis[i][k] + dis[k][j]
                    # Record that the shortest path from i to j passes through k
                    pos[i][j] = k

    return min_cycle_len, min_cycle_path


# --- Main program entry ---
if __name__ == "__main__":
    # Read number of nodes n and number of edges m
    n, m = map(int, sys.stdin.readline().split())

    # Read edge information
    edges = []
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        edges.append((u, v, w))

    # Find minimum cycle
    min_len, path = find_minimum_cycle_undirected(n, edges)

    # Output result
    if min_len == INF:
        print("No solution.")
    else:
        # Print path nodes (1-based index), separated by spaces
        print(" ".join(map(str, path)))

Example 2

GDOI2018 Day2 Patrol

Given an undirected graph with \(n\) points and no negative-weight edges, perform \(q\) operations of three types:

  1. Delete a point in the graph and its associated edges.
  2. Restore a deleted point and its associated edges.
  3. Query the size of the minimum cycle containing point \(x\).

For \(50\%\) of the data, \(n,q \le 100\).

For any simple cycle containing point \(x\), there exist two edges adjacent to \(x\). Deleting any one of them turns the simple cycle into a simple path.

Thus, enumerate all edges adjacent to \(x\), delete one each time, and run Dijkstra once.

Alternatively, run Floyd to find the minimum cycle for each query directly, \(O(qn^3)\).

For \(100\%\) of the data, \(n,q \le 400\).

Still use the Floyd algorithm for finding the minimum cycle.

If there is no deletion, removing the query point splits the simple cycle into a simple path.

However, the second step of solving is replaced by Floyd.

Thus, the answer requires the distance between any two points without passing through the query point \(x\).

How to handle online?

Force offline, using an offline method to avoid deletion operations.

Sort the queries in chronological order and build a segment tree over these queries.

The appearance time of each point covers all queries except the moments when the point is queried. Suppose a point is queried \(x\) times, then its appearance time can be considered as \(x + 1\) intervals, inserted into the segment tree.

After completion, traverse the entire segment tree. When entering a point, store a backup of the Floyd array, then add all points inserted in this interval. When leaving, restore using the backup array.

The time complexity of this approach is \(O(qn^2\log q)\).

There is also a more efficient online approach.

For a query on point \(x\), run a single-source shortest path from \(x\), then build the shortest path tree, and determine which subtree each point belongs to relative to \(x\).

Then, there must exist a non-tree edge whose two endpoints are in different subtrees of the root, such that this non-tree edge \(+\) the paths from the two endpoints to the root forms the minimum cycle.

Proof:

Clearly, the minimum cycle contains at least one non-tree edge with endpoints in different subtrees of the root.

Assume this edge is \((u,v)\). Then the path from \(x\) to \(u\) in the shortest path tree is the shortest among all paths from \(x\) to \(u\), and similarly for \(x\) to \(v\). Thus, the cycle \(x\to u\to v\to x\) cannot be longer than the minimum cycle.

Therefore, enumerate all non-tree edges and update the answer.

The complexity per query is that of running a single-source shortest path, \(O(n^2)\).

Total time complexity: \(O(qn^2)\).

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用