from collections import defaultdict
n, m, r, t, k = map(int, input().split())
graph = defaultdict(list)
matching = [-1] * m
degree = [0] * n
used = [0] * (n + 1)
T = 0
def try_dfs(v, deg):
global T
if used[v] == T:
return False
used[v] = T
if degree[v] > deg + 1:
return True
for u in graph[v]:
if try_dfs(matching[u], deg):
degree[matching[u]] -= 1
matching[u] = v
degree[v] += 1
return True
return False
for _ in range(k):
u, v = map(int, input().split())
u -= 1
v -= 1
graph[u].append(v)
for u in range(m):
if matching[u] == -1:
for v in range(n):
if u in graph[v] and matching[u] == -1:
matching[u] = v
degree[v] += 1
updated = True
while updated:
updated = False
ds = [(degree[v], v) for v in range(n)]
ds.sort()
T += 1
for _, v in ds:
if try_dfs(v, degree[v]):
updated = True
break
penalty = 0
res = []
for v in range(n):
degree[v] = min(degree[v], t // r)
for u in range(m):
if matching[u] != -1 and degree[matching[u]]:
penalty += degree[matching[u]] * r
degree[matching[u]] -= 1
res.append((matching[u] + 1, u + 1, degree[matching[u]] * r))
print(len(res), penalty)
for el in res:
print(el[0], el[1], el[2])
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
88 ms |
21796 KB |
Output is correct |
2 |
Correct |
85 ms |
21216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
19240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
128 ms |
24468 KB |
Output is correct |
2 |
Correct |
43 ms |
18744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
26640 KB |
Output is correct |
2 |
Correct |
256 ms |
26296 KB |
Output is correct |
3 |
Correct |
67 ms |
19340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
421 ms |
27148 KB |
Output is correct |
2 |
Correct |
427 ms |
28324 KB |
Output is correct |
3 |
Correct |
56 ms |
19588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
410 ms |
27596 KB |
Output is correct |
2 |
Correct |
314 ms |
26744 KB |
Output is correct |
3 |
Correct |
84 ms |
21292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
674 ms |
27684 KB |
Output is correct |
2 |
Correct |
359 ms |
28116 KB |
Output is correct |
3 |
Correct |
83 ms |
21352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
27660 KB |
Output is correct |
2 |
Correct |
478 ms |
27996 KB |
Output is correct |
3 |
Correct |
468 ms |
27956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
501 ms |
30144 KB |
Output is correct |
2 |
Correct |
52 ms |
19356 KB |
Output is correct |
3 |
Correct |
92 ms |
21836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
450 ms |
26352 KB |
Output is correct |
2 |
Correct |
826 ms |
28312 KB |
Output is correct |
3 |
Correct |
236 ms |
23292 KB |
Output is correct |