daily pastebin goal
41%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def get_equal_vertices(trails_for_hats, dual_solution):
  2.     equal_vertices = [False for _ in trails_for_hats]
  3.     for hat, trails_for_hat in enumerate(trails_for_hats):
  4.         trails_budget = sum([dual_solution[trail] for trail in trails_for_hat])
  5.         if trails_budget == costs[hat]:
  6.             equal_vertices[hat] = True
  7.     return equal_vertices
  8.  
  9.  
  10. def is_vertex_cover(equal_vertices, trails):
  11.     for trail_id, (u, v, w) in enumerate(trails):
  12.         if (not equal_vertices[u] and
  13.                 not equal_vertices[v] and
  14.                 not equal_vertices[w]):
  15.             return False, trail_id
  16.     return True, None
  17.  
  18. n, m = map(int, input().split())
  19. costs = [int(c_i) for c_i in input().split()]
  20. trails = []
  21. trails_for_hats = [[] for _ in range(n)]
  22. for i in range(m):
  23.     u, v, w = map(int, input().split())
  24.     trails.append((u - 1, v - 1, w - 1))
  25.     trails_for_hats[u - 1].append(i)
  26.     trails_for_hats[v - 1].append(i)
  27.     trails_for_hats[w - 1].append(i)
  28.  
  29. dual_solution = [0 for _ in range(m)]
  30. equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
  31. are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
  32. while not are_all_covered:
  33.     min_cost = min(costs[trails[uncovered_trail][0]],
  34.                    costs[trails[uncovered_trail][1]],
  35.                    costs[trails[uncovered_trail][2]])
  36.     dual_solution[uncovered_trail] += min_cost
  37.     equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
  38.     are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
  39. print(sum(equal_vertices))
  40. for i, is_in_cover in enumerate(equal_vertices):
  41.     if is_in_cover:
  42.         print(i + 1, end=' ')
  43. print()
  44. for y_e in dual_solution:
  45.     print(y_e, end=' ')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top