1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
from queue import Queue, LifoQueue
fences = dict()
tree = dict()
M = int(input()) # num pens
for i in range(M):
description = tuple(map(int,input().split()))
edges = description[0]
corners = []
for j in range(edges):
corners.append(description[j+1])
costs = []
for j in range(edges):
costs.append(description[j+1+edges])
for j,k in enumerate(corners):
if j == len(corners) -1:
next_corner = corners[0]
else:
next_corner = corners[j+1]
fences[(k, next_corner)] = costs[j]
if k in tree:
tree[k].add(next_corner)
else:
tree[k] = {next_corner}
if next_corner in tree:
tree[next_corner].add(k)
else:
tree[next_corner] = {k}
print(fences)
print(tree)
def deep_copy(dictionary):
out = dict()
for key,ele in zip(dictionary.keys(),dictionary.values()):
out[key] = ele.copy()
return out
q = Queue()
q.put(([],tree))
# for i in fences:
# q.put(([i], tree))
# tree[2].remove(3)
# tree[3].remove(2)
# tree[4].remove(5)
# tree[5].remove(4)
# tree[4].remove(7)
# tree[7].remove(4)
# q.put(([(2,3),(4,5),(4,7)], tree))
while not q.empty():
# current is list of fences removed, pen is the resulting tree
current, pen = q.get()
print("---------------------")
print(current, pen)
# check if this is solution
# if we form a loop when dfs then that is closed.
# we want maximum 1 (all animals in same pen)
# or 0 where animals break out then all must be 0 loops
is_solution = True
broken_out = False
node_loops = dict()
for i in pen.keys():
loops = -1
q2 = Queue()
q2.put((i,set()))
global_seen = set()
while not q2.empty():
c,seen = q2.get()
if c == i:
print("bad", loops,c,seen)
loops += 1
if loops > 0:
continue
# if loops > 1:
# is_solution = False
# break
if c in seen:
continue
else:
seen.add(c)
global_seen.add(c)
print(c, seen, loops, i)
for j in pen[c]:
q2.put((j,seen.copy()))
# print(c,j,seen, loops)
if loops == 0:
broken_out = True
print(loops, len(global_seen),len(pen.keys()))
if loops <= 2 and len(global_seen) == len(pen.keys()): # make sure there aren't isolated loops
node_loops[i] = loops
else:
is_solution = False
break
if broken_out:
for i in node_loops.values():
if i != 0:
is_solution = False
if is_solution:
output = 0
for i in current:
output += fences[i]
print("!", output, current, node_loops)
# find next
for fence in fences:
if fence not in current and (fence[1],fence[0]) not in current:
new_pen = deep_copy(pen)
new_pen[fence[0]].remove(fence[1])
new_pen[fence[1]].remove(fence[0])
print("#", fence, new_pen)
new_current = current[:]
new_current.append(fence)
q.put((new_current, deep_copy(new_pen)))
|
