Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def get_equal_vertices(trails_for_hats, dual_solution):
- equal_vertices = [False for _ in trails_for_hats]
- for hat, trails_for_hat in enumerate(trails_for_hats):
- trails_budget = sum([dual_solution[trail] for trail in trails_for_hat])
- if trails_budget == costs[hat]:
- equal_vertices[hat] = True
- return equal_vertices
- def is_vertex_cover(equal_vertices, trails):
- for trail_id, (u, v, w) in enumerate(trails):
- if (not equal_vertices[u] and
- not equal_vertices[v] and
- not equal_vertices[w]):
- return False, trail_id
- return True, None
- n, m = map(int, input().split())
- costs = [int(c_i) for c_i in input().split()]
- trails = []
- trails_for_hats = [[] for _ in range(n)]
- for i in range(m):
- u, v, w = map(int, input().split())
- trails.append((u - 1, v - 1, w - 1))
- trails_for_hats[u - 1].append(i)
- trails_for_hats[v - 1].append(i)
- trails_for_hats[w - 1].append(i)
- dual_solution = [0 for _ in range(m)]
- equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
- are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
- while not are_all_covered:
- min_cost = min(costs[trails[uncovered_trail][0]],
- costs[trails[uncovered_trail][1]],
- costs[trails[uncovered_trail][2]])
- dual_solution[uncovered_trail] += min_cost
- equal_vertices = get_equal_vertices(trails_for_hats, dual_solution)
- are_all_covered, uncovered_trail = is_vertex_cover(equal_vertices, trails)
- print(sum(equal_vertices))
- for i, is_in_cover in enumerate(equal_vertices):
- if is_in_cover:
- print(i + 1, end=' ')
- print()
- for y_e in dual_solution:
- print(y_e, end=' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement