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  s 0  t 0  w 0  s 1  t 1  w 1 : 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.  s i and t i represent source and target verticess of i -th directed edge. w i 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 ≤ w i ≤ 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

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

    
    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))

Solution (Python):
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]

        
        if i not in cycle_vertices:
            continue

        
        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))

Solution (Python):
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]

        
        if i not in cycle_vertices:
            continue

        
        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))

Solution (Python):
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)

Solution (Python):


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])



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):] 
                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)


print(edmonds_branching(G, r, 0))

Solution (Python):


V, E, r = list(map(int, input().split()))
es = [list(map(int, input().split())) for i in range(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 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:
                
                
                
                
                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(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]:
            
            
            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))

Solution (Python):



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))

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):



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()