• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Mar 23rd, 2019 72 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]],
34.                    costs[trails[uncovered_trail]],
35.                    costs[trails[uncovered_trail]])
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.

Top