转语言求助
  • 板块学术版
  • 楼主liuhaoyan0323
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/14 08:31
  • 上次更新2024/8/14 10:56:43
查看原帖
转语言求助
921177
liuhaoyan0323楼主2024/8/14 08:31

我有一个Python2代码,但是由于已经过时了,无法使用,有没有好人能把它改成至Python3或者C++语言,Python2我实在不懂。

class UnionFind(object):  # Time: (N * log*(N)), Space: O(N)
    def __init__(self, n):
        self.set = range(n)

    def get_id(self):
        self.set.append(len(self.set))
        return len(self.set)-1

    def find_set(self, x):
        stk = []
        while self.set[x] != x:  # path compression.
            stk.append(x)
            x = self.set[x]
        while stk:
            self.set[stk.pop()] = x
        return x

    def union_set(self, x, y):
        x_root, y_root = map(self.find_set, (x, y))
        if x_root == y_root:
            return False
        self.set[min(x_root, y_root)] = max(x_root, y_root)
        return True

def time_to_arrive(a, b):
    return (a+b)%24

def time_to_leave(a, b):
    return (b-a)%24

def mountain_tour():
    C = input()
    tours = map(lambda x: (x[0]-1, x[1], x[2]), [map(int, raw_input().strip().split()) for _ in xrange(2*C)])
    prev_camps = [[] for _ in xrange(C)]
    for i, (E, _, _) in enumerate(tours):
        prev_camps[E].append(i)
    result = sum(D for _, _, D in tours)
    next_camps, costs = [0]*(2*C), [0]*C
    for i, (prev_a, prev_b) in enumerate(prev_camps):
        if not i:
            ta = min(time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i][1]) + tours[2*i+1][1],
                     time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i+1][1]) + tours[2*i][1])
            tb = min(time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i+1][1]) + tours[2*i][1],
                     time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i][1]) + tours[2*i+1][1])
        else:
            ta = time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i][1]) + \
                 time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i+1][1])
            tb = time_to_leave(time_to_arrive(tours[prev_a][1], tours[prev_a][2]), tours[2*i+1][1]) + \
                 time_to_leave(time_to_arrive(tours[prev_b][1], tours[prev_b][2]), tours[2*i][1])
            assert(abs(ta-tb) in (0, 24))
        if ta < tb:
            result += ta
            next_camps[prev_a], next_camps[prev_b] = 2*i, 2*i+1
            costs[i] = tb-ta
        else:
            result += tb
            next_camps[prev_a], next_camps[prev_b] = 2*i+1, 2*i
            costs[i] = ta-tb
    union_find = UnionFind(2*C)
    for i in xrange(2*C):
        union_find.union_set(i, next_camps[i])
    for i, c in enumerate(costs):
        if not c:  # firstly, union tours with 0 hr
            union_find.union_set(2*i, 2*i+1)
    # secondly, union tours of camp1 if they are in disjoint cycles, which has the smallest union costs in the rest of disjoint cycles
    # finally, union the rest of tours in disjoint cycles, which all have the same cost 24 hrs
    return result + sum(c for i, c in enumerate(costs) if union_find.union_set(2*i, 2*i+1))


print ( mountain_tour())

2024/8/14 08:31
加载中...