Contest Duration: - (local time) (100 minutes) Back to Home

Submission #6036830

Source Code Expand

Copy
```from scipy.sparse.csgraph import dijkstra
# 二部グラフ完全マッチング
# 最大フロー
N = int(input())
NN = N * 2
XY = [[int(x) for x in input().split()] for _ in range(NN)]
graph = [[0] * (NN+2) for _ in range(NN+2)]
start = NN
goal = NN+1

for i,(a,b) in enumerate(XY[:N]):
for j,(c,d) in enumerate(XY[N:], N):
if a < c and b < d:
graph[i][j] = 1

for i in range(N):
graph[start][i] = 1
for i in range(N,NN):
graph[i][goal] = 1

INF = 10 ** 9

def max_flow(graph):
dist, pred = dijkstra(graph, indices = start, return_predecessors = True)
if dist[goal] > INF:
return 0
y = goal
while y != start:
x = pred[y]
graph[x][y] -= 1
graph[y][x] += 1
y = x
return 1 + max_flow(graph)

#### Submission Info

Submission Time 2019-06-21 12:20:38+0900 C - 2D Plane 2N Points maspy Python (3.4.3) 400 812 Byte AC 552 ms 15132 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
 AC × 5
 AC × 17
Set Name Test Cases
Sample example_0, example_1, example_2, example_3, example_4
All example_0, example_1, example_2, example_3, example_4, line_0, line_1, line_2, line_3, maxrand_0, maxrand_1, maxrand_2, maxrand_3, maxrand_4, rand_0, rand_1, rand_2
Case Name Status Exec Time Memory
example_0 AC 167 ms 13632 KB
example_1 AC 169 ms 13644 KB
example_2 AC 166 ms 13636 KB
example_3 AC 170 ms 13644 KB
example_4 AC 169 ms 13640 KB
line_0 AC 215 ms 14020 KB
line_1 AC 173 ms 14524 KB
line_2 AC 169 ms 14016 KB
line_3 AC 167 ms 13768 KB
maxrand_0 AC 509 ms 14996 KB
maxrand_1 AC 511 ms 15124 KB
maxrand_2 AC 501 ms 15124 KB
maxrand_3 AC 552 ms 15132 KB
maxrand_4 AC 483 ms 15000 KB
rand_0 AC 494 ms 14996 KB
rand_1 AC 246 ms 14272 KB
rand_2 AC 298 ms 14524 KB