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: Runtime Error

Solution code:
import heapq

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

in_edges = {v: set() for v in range(nv)}
out_edges = {v: set() for v in range(nv)}
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):
    global in_edges, out_edges, nv, r

    total_cost = 0
    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 be with branch from cycle)
        cycle_vertices, j = {i}, i
        while prev_v[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.add(nv)
        vertices -= cycle
        for v in cycle:
            for w, t in out_edges[v]:
                if t not in cycle:
                    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 not in cycle:
                    new_w = w - min(in_edges[v])[0]
                    in_edges[nv].add((new_w, s))
                    out_edges[s].remove((w, v))
                    out_edges[s].add((new_w, v))
        nv += 1

    return chu_liu_edmond(vertices)


print(chu_liu_edmond(set(range(nv))))

Submission status: Runtime Error

Solution code:
def edmond(V, paths, root):
  mins = [(10**18, -1)]*V
  for s,t,w in paths:
    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(mins[v][0] for v in xrange(V) if v != r and comp[group[v]])

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

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

V,E,r = map(int, raw_input().split())
paths = [map(int, raw_input().split()) for _ in xrange(E)]
print edmond(V, paths, r)

Submission status: Runtime Error

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[:root] + incoming_edges[root + 1:]:
        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):
    for edges in digraph:
        min_weight = edges[0][0]
        for e in edges:
            e[0] -= min_weight
    contracted_edges = []
    for n in cycle_node:
        edge_set_in_cycle = digraph[n]
        heapq.heappop(edge_set_in_cycle)
        for e in edge_set_in_cycle:
            heapq.heappush(contracted_edges, e)
    for n in cycle_node:
        digraph[n] = contracted_edges

            
def edmonds_branching(digraph, root, weight):
    min_incoming_edges = [None] * v_num
    for edges in digraph[:root] + digraph[root + 1:]:
        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)
        return edmonds_branching(digraph, root, weight)

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

Submission status: Runtime Error

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,(u,self.adj[X[0]][u]))

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

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

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



        return total_cost





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):
        ss=spaceinput()
        if not ss:
            break

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

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