-
Notifications
You must be signed in to change notification settings - Fork 0
/
uncompressed_solution.py
102 lines (84 loc) · 2.6 KB
/
uncompressed_solution.py
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
from collections import deque
INF = (1 << 64) - 1
def read_data():
n, k = [int(x) for x in input().split()]
sections = []
for _ in range(k):
sections.append(tuple([int(x) for x in input().split()]))
return n, k, sections
def all_points(section):
x1, y1, x2, y2 = section
points = []
for x in range(x1, x2 + 1):
for y in range(y1, y2 + 1):
points.append((x, y))
return points
def extract_data(sections):
rows = {}
columns = {}
points = []
for section in sections:
for row, column in all_points(section):
if not row in rows:
rows[row] = len(rows)
if not column in columns:
columns[column] = len(columns)
points.append((row, column))
points = [(rows[row], columns[column]) for row, column in points]
return points, rows, columns
def build_graph(points, n_rows, n_columns):
total_vertices = n_rows + n_columns + 2
graph = [[0 for _ in range(total_vertices)] for _ in range(total_vertices)]
source = total_vertices - 2
sink = total_vertices - 1
for row, column in points:
column += n_rows
graph[row][column] = INF
for i in range(n_rows):
graph[source][i] = 1
for i in range(n_columns):
graph[n_rows + i][sink] = 1
return graph
def BFS(graph, parents):
source = len(graph) - 2
sink = len(graph) - 1
visited = [False] * len(parents)
queue = deque([source])
visited[source] = True
while queue:
u = queue.popleft()
for ind, cap in enumerate(graph[u]):
if visited[ind] == False and cap > 0:
queue.append(ind)
visited[ind] = True
parents[ind] = u
if ind == sink:
return True
return False
def Edmonds_Karp(graph):
parents = [-1] * len(graph)
max_flow = 0
source = len(graph) - 2
sink = len(graph) - 1
while BFS(graph, parents):
path_flow = INF
s = sink
while s != source:
path_flow = min(path_flow, graph[parents[s]][s])
s = parents[s]
max_flow += path_flow
v = sink
while v != source:
u = parents[v]
graph[u][v] -= path_flow
graph[v][u] += path_flow
v = parents[v]
return max_flow
def main(sections=None):
if sections is None:
_, _, sections = read_data()
points, rows, columns = extract_data(sections)
graph = build_graph(points, len(rows), len(columns))
return Edmonds_Karp(graph)
if __name__ == "__main__":
main()