mirror of
https://github.com/iritmaximus/tira.git
synced 2026-10-12 19:13:47 +03:00
81 lines
2.1 KiB
Python
81 lines
2.1 KiB
Python
class MaximumFlow:
|
|
def __init__(self, nodes):
|
|
self.nodes = nodes
|
|
self.graph = {}
|
|
for i in self.nodes:
|
|
for j in self.nodes:
|
|
self.graph[(i, j)] = 0
|
|
|
|
def add_edge(self, node_a, node_b, capacity):
|
|
self.graph[(node_a, node_b)] += capacity
|
|
|
|
def add_flow(self, node, sink, flow):
|
|
if node in self.seen:
|
|
return 0
|
|
self.seen.add(node)
|
|
if node == sink:
|
|
return flow
|
|
for next_node in self.nodes:
|
|
if self.flow[(node, next_node)] > 0:
|
|
new_flow = min(flow, self.flow[(node, next_node)])
|
|
inc = self.add_flow(next_node, sink, new_flow)
|
|
if inc > 0:
|
|
self.flow[(node, next_node)] -= inc
|
|
self.flow[(next_node, node)] += inc
|
|
return inc
|
|
return 0
|
|
|
|
def construct(self, source, sink):
|
|
self.flow = self.graph.copy()
|
|
total = 0
|
|
while True:
|
|
self.seen = set()
|
|
add = self.add_flow(source, sink, float("inf"))
|
|
if add == 0:
|
|
break
|
|
total += add
|
|
return total
|
|
|
|
|
|
class Planets:
|
|
def __init__(self, n):
|
|
self.n = n
|
|
self.mf = MaximumFlow([x for x in range(1, n + 1)])
|
|
|
|
def add_teleport(self, a, b):
|
|
self.mf.add_edge(a, b, 1)
|
|
|
|
def min_removals(self):
|
|
return self.mf.construct(1, self.n)
|
|
|
|
|
|
class Planets2:
|
|
def __init__(self, n):
|
|
self.n = n
|
|
self.nodes = [x for x in range(1, n + 1)]
|
|
self.graph = {}
|
|
|
|
def add_teleport(self, a, b):
|
|
self.graph[b] = self.graph[b].append(a) if self.graph.get(b) else [a]
|
|
|
|
def min_removals(self):
|
|
nodes = self.graph[self.n]
|
|
lowest_teleports = 0
|
|
for x in nodes:
|
|
pass
|
|
|
|
return lowest_teleports
|
|
|
|
|
|
if __name__ == "__main__":
|
|
planets = Planets(5)
|
|
|
|
print(planets.min_removals()) # 0
|
|
|
|
planets.add_teleport(1, 2)
|
|
planets.add_teleport(2, 5)
|
|
print(planets.min_removals()) # 1
|
|
|
|
planets.add_teleport(1, 5)
|
|
print(planets.min_removals()) # 2
|