C++ 代码到 Python 的转换：最小生成树问题

import sys
from typing import List

class Edge:
    def __init__(self, u: int, v: int, g: int, s: int):
        self.u = u
        self.v = v
        self.g = g
        self.s = s

def find(x: int, fa: List[int]) -> int:
    if fa[x] == 0:
        return x
    fa[x] = find(fa[x], fa)
    return fa[x]

def main():
    n, m, wg, wS = map(int, sys.stdin.readline().split())
    a = [Edge(0, 0, 0, 0) for _ in range(m)]
    for i in range(m):
        a[i].u, a[i].v, a[i].g, a[i].s = map(int, sys.stdin.readline().split())
    a.sort(key=lambda x: x.g)
    ans = float('inf')
    fa = [0] * (n + 1)
    st = [0] * (n + 1)
    top = 0
    for i in range(m):
        for j in range(1, n + 1):
            fa[j] = 0
        for j in range(top, 0, -1):
            if a[st[j]].s > a[i].s:
                st[j + 1] = st[j]
            else:
                break
        top += 1
        st[j + 1] = i
        num = 0
        for j in range(1, top + 1):
            fu = find(a[st[j]].u, fa)
            fv = find(a[st[j]].v, fa)
            if fu != fv:
                fa[fu] = fv
                num += 1
                st[num] = st[j]
        if num == n - 1:
            ans = min(ans, wg * a[i].g + wS * a[st[num]].s)
        top = num
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

这段代码使用 Python 语言实现了与 C++ 代码相同的算法，即 Kruskal 算法，用于解决最小生成树问题。以下是代码的解释：

• 类 Edge： 用于表示图中的边，包含边的两个节点 (u, v)、边权 (g) 和特殊权值 (s)。
• 函数 find： 用于实现并查集，查找节点所属的集合。
• 主函数 main：
  • 读取输入：读取图的节点数 n、边数 m、边权系数 wg 和特殊权值系数 wS，以及每条边的信息（u, v, g, s)。
  • 排序：按照边权 g 对边进行排序。
  • 变量初始化： ans 用于保存最小生成树的权值，fa 用于并查集，st 用于保存当前已加入生成树的边，top 表示 st 中边的数量。
  • 循环遍历边：
    • 遍历每条边 i，使用并查集判断边 i 是否能加入生成树，并更新 st 和 top。
    • 如果当前生成树包含 n - 1 条边，则更新 ans。
• 最后输出 ans 或 -1（表示无解）。

代码的关键在于使用并查集算法，在每一步添加边时判断该边是否能将两个不同的集合连通，避免出现环路。

请注意，这段 Python 代码与原始 C++ 代码的功能相同，但在实现方式上有所不同。例如，C++ 代码使用 qsort 函数进行排序，而 Python 代码使用 sort 方法进行排序。

希望这个解释对您有所帮助。如果您还有其他问题，请随时提出。