Python의 모든 정점 중 그래프 내 최소 비용의 합을 찾는 프로그램

<시간/>

n개의 꼭짓점과 m개의 모서리가 있는 가중치 그래프가 있다고 가정합니다. 간선의 가중치는 2입니다. 모든 정점은 그래프의 모든 정점에서 도달할 수 있으며 이동 비용은 그래프의 모든 간선 가중치를 더한 것입니다. 각 정점 쌍 사이의 최소 비용 합계를 결정해야 합니다.

따라서 입력이 다음과 같으면

그리고 정점의 수(n) =6; 그러면 출력은 2696이 됩니다.

모든 거리의 합은 2696입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

par_finder() 함수를 정의합니다. 이것은 내가 걸릴 것입니다, par
- par[i]가 -1과 같으면
  - 반환
- res :=par_finder(par[i], par)
- par[i] :=res
- 반환 결과
helper() 함수를 정의합니다. 이것은 i, par, w, G, n
- 자식 :=1
- G[i]의 각 항목에 대해 다음을 수행합니다.
  - item[0]이 par와 같으면
    - 다음 반복으로 이동
  - 그렇지 않으면
    - child :=자식 + 도우미(item[0], i, item[1], G, n)
  - par이 -1과 같지 않으면
    - ans :=ans + 자식 * (n - 자식) *(1 * 2^w)
  - 반환 자녀
G :=n + 1개의 다른 목록을 포함하는 새 목록
가장자리 :=새 목록
도로의 각 항목에 대해 다음을 수행합니다.
- u :=항목[0]
- v :=항목[1]
- w :=항목[2]
- 가장자리 끝에 (u-1, v-1, w) 삽입
가장자리 가중치를 기준으로 목록 가장자리 정렬
par :=-1로 초기화된 크기 n + 1의 새 목록
r_edge :=새 목록
가장자리의 각 i에 대해 다음을 수행합니다.
- par_finder(i[0], par)가 par_finder(i[1], par)와 같으면
  - 다음 반복으로 이동
- 그렇지 않으면
  - r_edge 끝에 i 삽입
  - G[i[0]] 끝에 쌍(i[1],i[2]) 삽입
  - G[i[1]] 끝에 쌍(i[0],i[2]) 삽입
  - par[par_finder(i[0], par)] :=par_finder(i[1], par)
ans :=0
도우미(0, -1, 0, G, n)
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def par_finder(i, par) :
    if par[i] == -1 :
         return i
    res = par_finder(par[i], par)
    par[i] = res
    return res

def helper(i, par, w, G, n) :
    global ans
    child = 1
    for item in G[i] :
        if item[0] == par :
            continue
        else :
            child += helper(item[0],i,item[1], G, n)
    if par != -1 :
        ans += child * (n - child) * (1 << w)
    return child

def solve(n, roads):
    global ans
    G = [[] for i in range(n + 1)]
    edges = []
    for item in roads :
        u,v,w = map(int, item)
        edges.append((u-1, v-1, w))
    edges = sorted(edges,key = lambda item : item[2])
    par = [-1 for i in range(n + 1)]
    r_edge = []
    for i in edges :
        if par_finder(i[0], par) == par_finder(i[1], par) :
            continue
        else :
            r_edge.append(i)
            G[i[0]].append((i[1],i[2]))
            G[i[1]].append((i[0],i[2]))
            par[par_finder(i[0], par)] = par_finder(i[1], par)
    ans = 0      
    helper(0, -1, 0, G, n)
    return ans

print(solve(6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]))

입력

6, [(1,4,8), (2,4,4), (3,4,4), (3,4,2), (5,3,8), (6,3,2)]