Problem:


Minimum-Cost Arborescence

Find the sum of the weights of edges of the Minimum-Cost Arborescence with the root r for a given weighted directed graph G = (V, E).

Input

|V| |E| r
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the root of the Minimum-Cost Arborescence.

si and ti represent source and target verticess of i-th directed edge. wi represents the weight of the i-th directed edge.

Output

Print the sum of the weights the Minimum-Cost Arborescence.

Constraints

1 ≤ |V| ≤ 100

0 ≤ |E| ≤ 1,000

0 ≤ wi ≤ 10,000

G has arborescence(s) with the root r

Sample Input 1

4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5

Sample Output 1

6

Sample Input 2

6 10 0
0 2 7
0 1 1
0 3 5
1 4 9
2 1 6
1 3 2
3 4 3
4 2 2
2 5 8
3 5 3

Sample Output 2

11



Sample input:
4 6 0
0 1 3
0 2 2
2 0 1
2 3 1
3 0 1
3 1 5


Sample output:
6

Submission status: Wrong Answer

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # ??°????????????????????°
        #dist = [float('inf') for i in range(N)] # ?§????????????????????????§??????????????¢???????´???????
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):
        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(self.adj[X[0]][u],u))

        total_cost=0
        while True:
            #print(unused)
            cost,v=heapq.heappop(unused)

            X.append(v)
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                if u in X:
                    continue
                heapq.heappush(unused,(self.adj[v][u],u))

        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for u in self.adj:
            for v in self.adj[u]:

                #G.add_edge(e.node_from,e.node_to,weight=e.cost)
                G.add_edge(u,v,weight=self.adj[u][v])
                #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    a=spaceinput()
    g=myGraph()


    for i in range(999):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),ss[2])
        #g.add_directed_edge((ss[0],ss[1]),ss[2])

    #print(g.show())
    print(g.prim())

    '''
    d=g.dijkstra(1)
    '''



    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''

Submission status: Time Limit Exceeded

Solution code:
def cycle_cost(cycles, m):
    return sum(m[ci] for cycle in cycles for ci in cycle)

def get_cycle(pre, nxt, root):
    cycles, checked = [], set()

    # root?????£????????????????????????????????§?????????????????????
    checked |= {root}
    que = nxt[root][:]
    while que:
        root_linked = que.pop()
        checked |= {root_linked}
        if nxt[root_linked]:
            que.extend(nxt[root_linked])

    for i in range(len(pre)):
        if i in checked:
            continue

        # ?????°????????§???????????????????????????
        checking = set()
        while i not in checked:
            checked |= {i}
            checking |= {i}
            i = pre[i]
        if i not in checking: # ?????°????????????
            continue

        # ??????????????´???????????????????????°??¨????????¢???   
        checking.clear()
        while i not in checking:
            checking |= {i}
            i = pre[i]            
            
        cycles.append(checking)
    return cycles

from collections import defaultdict
from itertools import product
def chi_liu_edmonds(g, v, r):
    # ?°??????????????????????????±??????????
    m = [float('inf')] * v
    pre = [None] * v
    nxt = defaultdict(list)
    for s, t in product(range(v), repeat=2):
        if g[s][t] < m[t]:
            m[t] = g[s][t]
            pre[t] = s
            nxt[s].append(t)

    cycles = get_cycle(pre, nxt, r)

    # ??¨??¨??£?????????????????´???
    if len(cycles) == 0:
        m[r] = 0
        return sum(m)
    
    not_cycle = set(range(v)).difference(cycles)
    #????´????????????????
    abridger  = {ni:i for i, ni in enumerate(not_cycle)}
    abridger.update({ci:i + len(not_cycle) for i, cycle in enumerate(cycles) for ci in cycle})
    
    v_dash = len(not_cycle) + len(cycles)
    g_dash = [[float('inf')] * v_dash for _ in range(v_dash)]
    for s, t in product(range(v), repeat=2):
        s_dash, t_dash = abridger[s], abridger[t]
        if s_dash != t_dash:
            d = g[s][t] if t in not_cycle else g[s][t] - g[pre[t]][t]
            g_dash[s_dash][t_dash] = d
    return chi_liu_edmonds(g_dash, v_dash, converter[r]) + cycle_cost(cycles, m)

from sys import stdin
readline = stdin.readline

v, e, r = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]

for _ in range(e):
    s, t, d = map(int, readline().split())
    if t == r:
        continue
    g[s][t] = d
print(chi_liu_edmonds(g, v, r))

Submission status: Accepted

Solution code:
def get_cycle(pre, nxt, root):
    cycles, checked = [], set()

    # root?????£????????????????????????????????§?????????????????????
    checked |= {root}
    que = nxt[root][:]
    while que:
        root_linked = que.pop()
        checked |= {root_linked}
        if nxt[root_linked]:
            que.extend(nxt[root_linked])

    for i in range(len(pre)):
        if i in checked:
            continue

        # ?????°????????§???????????????????????????
        checking = set()
        while i not in checked:
            checked |= {i}
            checking |= {i}
            i = pre[i]
        if i not in checking: # ?????°????????????
            continue

        # ??????????????´???????????????????????°??¨????????¢???   
        checking.clear()
        while i not in checking:
            checking |= {i}
            i = pre[i]            
            
        cycles.append(checking)
    return cycles

def cycle_cost(cycles, m):
    return sum(m[ci] for cycle in cycles for ci in cycle)

from collections import defaultdict
from itertools import product
def chi_liu_edmonds(g, v, r):
    # ?°??????????????????????????±??????????
    m = [float('inf')] * v
    pre = [None] * v
    for s, t in product(range(v), repeat=2):
        if g[s][t] < m[t]:
            m[t] = g[s][t]
            pre[t] = s
    nxt = defaultdict(list)
    for t, s in enumerate(pre):
        if s is not None:
            nxt[s].append(t)

    cycles = get_cycle(pre, nxt, r)

    # ??¨??¨??£?????????????????´???
    if len(cycles) == 0:
        m[r] = 0
        return sum(m)
    
    not_cycle = set(range(v)).difference(*cycles)
    #????´????????????????
    abridger  = {ni:i for i, ni in enumerate(not_cycle)}
    abridger.update({ci:i + len(not_cycle) for i, cycle in enumerate(cycles) for ci in cycle})
    v_dash = len(not_cycle) + len(cycles)
    g_dash = [[float('inf')] * v_dash for _ in range(v_dash)]
    for s, t in product(range(v), repeat=2):
        s_dash, t_dash = abridger[s], abridger[t]
        if s_dash != t_dash:
            d = g[s][t] if t in not_cycle else g[s][t] - g[pre[t]][t]
            if g_dash[s_dash][t_dash] > d:
                g_dash[s_dash][t_dash] = d
    return chi_liu_edmonds(g_dash, v_dash, abridger[r]) + cycle_cost(cycles, m)

from sys import stdin
readline = stdin.readline

v, e, r = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]

for _ in range(e):
    s, t, d = map(int, readline().split())
    if t == r:
        continue
    g[s][t] = d
print(chi_liu_edmonds(g, v, r))

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import chain

nv, ne, r = map(int, input().split())

in_edges = defaultdict(set)
out_edges = defaultdict(set)
while ne:
    s, t, w = map(int, input().split())
    in_edges[t].add((w, s))
    out_edges[s].add((w, t))
    ne -= 1


def chu_liu_edmond(vertices, cycle_cost):
    global in_edges, out_edges, nv, r

    total_cost = cycle_cost
    prev_v = {v: None for v in vertices}
    next_vs = {v: set() for v in vertices}

    for t in vertices:
        if t == r:
            continue
        min_in_w, min_in_s = min(in_edges[t])
        total_cost += min_in_w
        prev_v[t] = min_in_s
        next_vs[min_in_s].add(t)

    visited = {r}
    queue = set(next_vs[r])
    while queue:
        t = queue.pop()
        visited.add(t)
        queue.update(next_vs[t])

    cycles = []
    for i in vertices:
        if i in visited:
            continue

        cycle_vertices = set()
        while i not in visited:
            visited.add(i)
            cycle_vertices.add(i)
            i = prev_v[i]

        # Branched single path from cycle
        if i not in cycle_vertices:
            continue

        # Current cycle_vertices are not necessarily cycle (may contain branch from cycle)
        cycle_vertices, j = {i}, prev_v[i]
        while j != i:
            cycle_vertices.add(j)
            j = prev_v[j]

        cycles.append(cycle_vertices)

    if not cycles:
        return total_cost

    for cycle in cycles:
        vertices.difference_update(cycle)
        vertices.add(nv)

        for v in cycle:
            prev_e_cost = min(in_edges[v])[0]
            cycle_cost += prev_e_cost
            for w, t in out_edges[v]:
                if t in vertices:
                    out_edges[nv].add((w, t))
                    in_edges[t].remove((w, v))
                    in_edges[t].add((w, nv))
            for w, s in in_edges[v]:
                if s in vertices:
                    new_w = w - prev_e_cost
                    in_edges[nv].add((new_w, s))
                    out_edges[s].remove((w, v))
                    out_edges[s].add((new_w, nv))
            del in_edges[v]
            del out_edges[v]

        nv += 1

    return chu_liu_edmond(vertices, cycle_cost)


print(chu_liu_edmond(set(range(nv)), 0))

Submission status: Accepted

Solution code:
from collections import defaultdict

nv, ne, r = map(int, input().split())

in_edges = defaultdict(set)
out_edges = defaultdict(set)
while ne:
    s, t, w = map(int, input().split())
    in_edges[t].add((w, s))
    out_edges[s].add((w, t))
    ne -= 1


def chu_liu_edmond(vertices, cycle_cost):
    global in_edges, out_edges, nv, r

    total_cost = cycle_cost
    prev_v = defaultdict(int)
    next_vs = defaultdict(set)

    for t in vertices:
        if t == r:
            continue
        min_in_w, min_in_s = min(in_edges[t])
        total_cost += min_in_w
        prev_v[t] = min_in_s
        next_vs[min_in_s].add(t)

    visited = {r}
    queue = set(next_vs[r])
    while queue:
        t = queue.pop()
        visited.add(t)
        queue.update(next_vs[t])

    cycles = []
    for i in vertices:
        if i in visited:
            continue

        cycle_vertices = set()
        while i not in visited:
            visited.add(i)
            cycle_vertices.add(i)
            i = prev_v[i]

        # Branched single path from cycle
        if i not in cycle_vertices:
            continue

        # Current cycle_vertices are not necessarily cycle only (may contain branch)
        cycle_vertices, j = {i}, prev_v[i]
        while j != i:
            cycle_vertices.add(j)
            j = prev_v[j]

        cycles.append(cycle_vertices)

    if not cycles:
        return total_cost

    for cycle in cycles:
        vertices.difference_update(cycle)
        vertices.add(nv)

        for v in cycle:
            prev_e_cost = min(in_edges[v])[0]
            cycle_cost += prev_e_cost
            for w, t in out_edges[v]:
                if t in vertices:
                    out_edges[nv].add((w, t))
                    in_edges[t].remove((w, v))
                    in_edges[t].add((w, nv))
            for w, s in in_edges[v]:
                if s in vertices:
                    new_w = w - prev_e_cost
                    in_edges[nv].add((new_w, s))
                    out_edges[s].remove((w, v))
                    out_edges[s].add((new_w, nv))
            del in_edges[v]
            del out_edges[v]

        nv += 1

    return chu_liu_edmond(vertices, cycle_cost)


print(chu_liu_edmond(set(range(nv)), 0))

Submission status: Accepted

Solution code:
V, E, r = map(int, raw_input().split())
es = [map(int, raw_input().split()) for i in xrange(E)]

def solve(V, es, r):
    mins = [(10**18, -1)]*V
    for s, t, w in es:
        mins[t] = min(mins[t], (w, s))
    mins[r] = (-1, -1)

    group = [0]*V
    comp = [0]*V
    cnt = 0

    used = [0]*V
    for v in xrange(V):
        if not used[v]:
            chain = []
            cur = v
            while not used[cur] and cur!=-1:
                chain.append(cur)
                used[cur] = 1
                cur = mins[cur][1]
            if cur!=-1:
                cycle = 0
                for e in chain:
                    group[e] = cnt
                    if e==cur:
                        cycle = 1
                        comp[cnt] = 1
                    if not cycle:
                        cnt += 1
                if cycle:
                    cnt += 1
            else:
                for e in chain:
                    group[e] = cnt
                    cnt += 1


    if cnt == V:
        return sum(map(lambda x:x[0], mins)) + 1

    res = sum(comp[group[v]]*mins[v][0] for v in xrange(V) if v!=r)

    n_es = []
    for s, t, w in es:
        gs = group[s]; gt = group[t]
        if gs == gt:
            continue
        if comp[gt]:
            n_es.append((gs, gt, w - mins[t][0]))
        else:
            n_es.append((gs, gt, w))

    return res + solve(cnt, n_es, group[r])

print solve(V, es, r)

Submission status: Accepted

Solution code:
# Acceptance of input

import sys

file_input = sys.stdin

v_num, e_num, r = map(int, file_input.readline().split())

G = [[] for i in range(v_num)]

import heapq

for line in file_input:
    s, t, w = map(int, line.split())
    if t != r:
        heapq.heappush(G[t], [w, s, t])

# Edmonds' algorithm

def find_cycle(incoming_edges, root):
    in_tree = [False] * v_num
    in_tree[root] = True
    for e in incoming_edges:
        if e:
            S = []
            S.append(e[2])
            while True:
                p = incoming_edges[S[-1]][1]
                if in_tree[p]:
                    while S:
                        in_tree[S.pop()] = True
                    break
                elif p in S:
                    return S[S.index(p):] # return nodes in a cycle
                else:
                    S.append(p)
    return None

def contract_cycle(digraph, cycle_node, root):
    super_node = cycle_node[0]
    for edges in digraph:
        if edges:
            min_weight = edges[0][0]
            for e in edges:
                e[0] -= min_weight
                if e[1] in cycle_node:
                    e[1] = super_node
                if e[2] in cycle_node:
                    e[2] = super_node
    contracted_edges = []
    for n in cycle_node: 
        for e in digraph[n]:
            if e[1] != super_node:
                heapq.heappush(contracted_edges, e)
        digraph[n].clear()
    digraph[super_node] = contracted_edges

def edmonds_branching(digraph, root, weight):
    min_incoming_edges = [None] * v_num
    for edges in digraph:
        if edges:
            min_edge = edges[0]
            min_incoming_edges[min_edge[2]] = min_edge
            weight += min_edge[0]
    C = find_cycle(min_incoming_edges, root)
    if not C:
        return weight
    else:
        contract_cycle(digraph, C, r)
        return edmonds_branching(digraph, root, weight)

# output
print(edmonds_branching(G, r, 0))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1850894#1)
V, E, r = list(map(int, input().split()))
es = [list(map(int, input().split())) for i in range(E)]

# 以下を参考にさせていただきました
# http://ti2236.hatenablog.com/entry/2012/12/07/175841

# Chu-Liu/Edmonds' Algorithm
# 最小全域有向木を再帰的に求める
# V: 頂点数, es: 辺集合, r: 根となる頂点番号
def solve(V, es, r):
    # まず、頂点vに入るものの内、コストが最小の辺を選択する
    # minsには(最小コスト, その辺のもう一方の頂点番号)
    mins = [(10**18, -1)]*V
    for s, t, w in es:
        mins[t] = min(mins[t], (w, s))
    # 根となる頂点rからは何も選択しない
    mins[r] = (-1, -1)

    group = [0]*V # 縮約した際に割り振られる頂点番号
    comp = [0]*V  # 縮約されたgroupか
    cnt = 0       # 縮約した後の頂点数

    # 縮約処理
    used = [0]*V
    for v in range(V):
        if not used[v]:
            chain = [] # 探索時に通った頂点番号リスト
            cur = v    # 現在探索中の頂点
            while not used[cur] and cur!=-1:
                chain.append(cur)
                used[cur] = 1
                cur = mins[cur][1]
            if cur!=-1:
                # 探索が根の頂点rで終了しなかった場合
                # chain = [a0, a1, ..., a(i-1), ai, ..., aj], cur = aiの場合
                # a0, ..., a(i-1)までは固有の番号を割り振り
                # ai, ..., ajまでは閉路であるため、同じ番号を割り振るようにする
                cycle = 0
                for e in chain:
                    group[e] = cnt
                    if e==cur:
                        # 閉路を見つけた
                        cycle = 1
                        comp[cnt] = 1
                    if not cycle:
                        cnt += 1
                if cycle:
                    cnt += 1
            else:
                # 探索が根の頂点rで終了した場合
                # --> 閉路を持たないため、１つずつ新しい番号を割り振っていく
                for e in chain:
                    group[e] = cnt
                    cnt += 1

    # cntがV => 閉路が存在せず、有向木が構築できている
    if cnt == V:
        # 根の頂点r以外が選択した辺のコストの和を返す
        # (+1はmins[r][0]の-1を打ち消すやつ)
        return sum(map(lambda x:x[0], mins)) + 1

    # 閉路が含まれていた場合
    # --> 閉路に含まれている頂点が選択した辺のコストの和を計算
    res = sum(mins[v][0] for v in range(V) if v!=r and comp[group[v]])

    # 再帰的に計算するグラフが持つ辺を構築
    n_es = []
    for s, t, w in es:
        # 追加する辺に繋がる頂点は、新しいグラフの頂点番号に変換する
        gs = group[s]; gt = group[t]
        if gs == gt:
            # 同じ閉路に含まれている頂点どうしをつなぐ辺の場合
            # --> 追加しない
            continue
        if comp[gt]:
            # ある閉路に含まれている頂点vに入る辺の場合
            # --> その辺のコストから、閉路においてその頂点vに入っていた辺のコストを引く
            n_es.append((gs, gt, w - mins[t][0]))
        else:
            # その他 --> 何もせず追加
            n_es.append((gs, gt, w))

    # 再帰的に求めた最小コストと、さっき計算したコストresを足したものを返す
    return res + solve(cnt, n_es, group[r])

print(solve(V, es, r))

Submission status: Accepted

Solution code:
# AOJ GRL_2_B
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B

import sys
from heapq import heappush, heappop

V, E, r = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for _ in range(0, E)]

def solve(V, Edge, r):
    if V <= 1:
        return 0
    q = [[] for _ in range(0, V)]
    for s, t, w in Edge:
        heappush(q[t], (w, s))
    M = [(0, -1) for _ in range(0, V)]
    for t in range(0, V):
        if t != r:
            w, s = heappop(q[t])
            M[t] = (w, s)
    
    used = [False for _ in range(0, V)]
    hist = []
    cycle = []
    for t in range(0, V):
        w, s = M[t]
        if s == -1 or used[t] == True:
            continue
        if used[t] == False:
            used[t] = True
            hist += [t]
            tt = s
            while used[tt] == False:
                used[tt] = True
                hist += [tt]
                w, s = M[tt]
                if s == -1:
                    hist = []
                    break
                tt = s
            if used[tt] == True and s != -1 and 0 < len(hist):
                try:
                    k = hist.index(tt)
                    cycle = hist[k:]
                except:
                    continue
                finally:
                    pass
                break
                
    if len(cycle) == 0:
        return sum(m[0] for m in M)

    parent = min(cycle)
    rn = [0 for _ in range(0, V)]
    k = 0
    for t in range(0, V):
        if k == parent:
            k += 1
        if t in cycle:
            rn[t] = parent
        else:
            rn[t] = k
            k += 1
            
    Vp = V - len(cycle) + 1
    Ep = []
    for s, t, w in Edge:
        if s in cycle:
            if t in cycle:
                continue
            else:
                Ep += [[parent, rn[t], w]]
        else:
            if t in cycle:
                Ep += [[rn[s], parent, w - M[t][0]]]
            else:
                Ep += [[rn[s], rn[t], w]]
    r = rn[r]
    return solve(Vp, Ep, r) + sum(M[t][0] for t in cycle)

print(solve(V, Edge, r))

Submission status: Accepted

Solution code:
import heapq
from typing import List, Optional


def _find_cycle(incoming_edges: List[List[int]], root: int) -> Optional[List[int]]:
    in_tree = [False] * v_num
    in_tree[root] = True
    for e in incoming_edges:
        if e:
            S = []
            S.append(e[2])
            while True:
                p = incoming_edges[S[-1]][1]
                if in_tree[p]:
                    while S:
                        in_tree[S.pop()] = True
                    break
                elif p in S:
                    return S[S.index(p):]
                else:
                    S.append(p)
    return None


def _contract_cycle(digraph: List[List[List[int]]],
                    cycle_node: List[int], root: int) -> None:
    super_node = cycle_node[0]
    for edges in digraph:
        if edges:
            min_weight = edges[0][0]
            for e in edges:
                e[0] -= min_weight
                if e[1] in cycle_node:
                    e[1] = super_node
                if e[2] in cycle_node:
                    e[2] = super_node
    contracted_edges: List[List[int]] = []
    for n in cycle_node:
        for e in digraph[n]:
            if e[1] != super_node:
                heapq.heappush(contracted_edges, e)
        digraph[n].clear()
    digraph[super_node] = contracted_edges


def edmonds_branching(digraph: List[List[List[int]]], root: int, weight: int) -> int:
    min_incoming_edges: List[List[int]] = [[]] * v_num
    for edges in digraph:
        if edges:
            min_edge = edges[0]
            min_incoming_edges[min_edge[2]] = min_edge
            weight += min_edge[0]
    C = _find_cycle(min_incoming_edges, root)
    if not C:
        return weight
    else:
        _contract_cycle(digraph, C, r)
        return edmonds_branching(digraph, root, weight)


if __name__ == "__main__":
    v_num, e_num, r = map(lambda x: int(x), input().split())
    G: List[List[List[int]]] = [[] for i in range(v_num)]

    for _ in range(e_num):
        s, t, w = map(lambda x: int(x), input().split())
        if t != r:
            heapq.heappush(G[t], [w, s, t])

    print(edmonds_branching(G, r, 0))

Submission status: Accepted

Solution code:
def input(f):
    global v, e, r
    global s, t, w
    
    v, e, r = map(int, f.readline().split())
    s = []
    t = []
    w = []
    for _ in range(e):
        s_, t_, w_ = map(int, f.readline().split())
        s.append(s_)
        t.append(t_)
        w.append(w_)

def solve(v, edges, r):
    best = [(10**18, -1) for _ in range(v)]
    for s, t, w in edges:
        best[t] = min(best[t], (w, s))
    best[r] = (0, -1)
    
    group = [0] * v
    comp = [0] * v
    used = [0] * v
    cnt = 0
    for i in range(v):
        if used[i]:
            continue
        
        chain = []
        cur = i
        
        while not used[cur] and cur != -1:
            chain.append(cur)
            used[cur] = 1
            cur = best[cur][1]
        
        if cur != -1:
            cycle = 0
            for x in chain:
                group[x] = cnt
                if x == cur:
                    cycle = 1
                    comp[cnt] = 1
                if not cycle:
                    cnt += 1
            if cycle:
                cnt += 1
        else:
            for x in chain:
                group[x] = cnt
                cnt += 1
    
    if cnt == v:
        return sum(map(lambda x: x[0], best))
    
    next_edges = []
    for s, t, w in edges:
        gs = group[s]
        gt = group[t]
        if gs == gt:
            continue
        if comp[gt]:
            next_edges.append((gs, gt, w - best[t][0]))
        else:
            next_edges.append((gs, gt, w))
    
    res = sum(best[x][0] for x in range(v) if x != r and comp[group[x]])
    return res + solve(cnt, next_edges, group[r])

with open('/dev/stdin') as f:
    input(f)

    edges = []
    for i in range(e):
        edges.append((s[i], t[i], w[i]))
    res = solve(v, edges, r)

    print(res)

Submission status: Accepted

Solution code:
# Edige Weighted Digraph


from collections import namedtuple


WeightedEdge = namedtuple('WeightedEdge', ('src', 'dest', 'weight'))


class Digraph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def mca_chu_liu_edmonds(graph, s):
    def select_edges():
        es = [None] * graph.v
        for v in range(graph.v):
            for e in graph.adj(v):
                w = e.dest
                if w == s:
                    continue
                if es[w] is None or e.weight < es[w].weight:
                    es[w] = e
        return es

    def find_cycle(es):
        vs = [0 for _ in range(graph.v)]
        for e in es:
            if e is None:
                continue
            vs[e.src] += 1
        leaves = [v for v, c in enumerate(vs) if c == 0]
        while leaves:
            leaf, *leaves = leaves
            if es[leaf] is not None:
                w = es[leaf].src
                vs[w] -= 1
                if vs[w] == 0:
                    leaves.append(w)
        cycle = []
        for v, c in enumerate(vs):
            if c > 0:
                cycle.append(v)
                u = es[v].src
                while u != v:
                    cycle.append(u)
                    u = es[u].src
                break
        return cycle

    def contract(es, vs):
        vvs = []
        vv = 0
        c = graph.v - len(vs)
        for v in range(graph.v):
            if v in vs:
                vvs.append(c)
            else:
                vvs.append(vv)
                vv += 1
        g = Digraph(c+1)
        for v in range(graph.v):
            for e in graph.adj(v):
                if e.src not in vs or e.dest not in vs:
                    v = vvs[e.src]
                    w = vvs[e.dest]
                    weight = e.weight
                    if e.dest in vs:
                        weight -= es[e.dest].weight
                    e = WeightedEdge(v, w, weight)
                    g.add(e)
        return g, vvs[s]

    edges = select_edges()
    cycle = find_cycle(edges)

    if cycle:
        g, ss = contract(edges, cycle)
        return mca_chu_liu_edmonds(g, ss) + sum(edges[v].weight for v in cycle)
    else:
        return sum(e.weight for e in edges if e is not None)


def run():
    v, e, r = [int(i) for i in input().split()]
    graph = Digraph(v)

    for _ in range(e):
        s, t, w = [int(i) for i in input().split()]
        graph.add(WeightedEdge(s, t, w))

    print(mca_chu_liu_edmonds(graph, r))


if __name__ == '__main__':
    run()