[백준 2126] 지진
1. 문제 설명
2. 문제 분석
이분 탐색을 통해 MST에서 사용할 이득 수식의 x
(mid
)를 결정한다. 정렬/우선순위 큐를 통해 이득을 최대화할 수 있다.
- 이득을 표현하는 수식을 찾고, 이를 MST를 찾을 때 정렬하는 키로 삼아야 하는, 두 가지 개념을 혼합한 문제.
3. 나의 풀이
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(mid):
pq = sorted(edges, key=lambda x:(x[2]+x[3]*mid))
# 우선순위 큐로 cost + time * x 오름차순 정렬
total = 0
for edge in pq:
node1, node2, cost, time = edge
if union(node1, node2):
total += (cost + time * mid)
if total <= f: return True
# f보다 작다면 이득이 양수
else: return False
n, m, f = map(int, sys.stdin.readline().rstrip().split())
edges = deque()
for _ in range(m):
a, b, c, t = map(int, sys.stdin.readline().rstrip().split())
edges.append([a, b, c, t])
left, right = 0, sys.maxsize
for _ in range(500):
parents = [i for i in range(n+1)]
mid = (left + right) / 2
# 이득 x = (f-total cost) / total time
# f = x * total time + total cost
if Kruskal(mid):
left = mid
else:
right = mid
if mid < 0: print("0.0000")
else: print(f"{mid:.4f}")
Author And Source
이 문제에 관하여([백준 2126] 지진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-2126-지진
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
이분 탐색을 통해 MST에서 사용할 이득 수식의
x
(mid
)를 결정한다. 정렬/우선순위 큐를 통해 이득을 최대화할 수 있다.
- 이득을 표현하는 수식을 찾고, 이를 MST를 찾을 때 정렬하는 키로 삼아야 하는, 두 가지 개념을 혼합한 문제.
3. 나의 풀이
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(mid):
pq = sorted(edges, key=lambda x:(x[2]+x[3]*mid))
# 우선순위 큐로 cost + time * x 오름차순 정렬
total = 0
for edge in pq:
node1, node2, cost, time = edge
if union(node1, node2):
total += (cost + time * mid)
if total <= f: return True
# f보다 작다면 이득이 양수
else: return False
n, m, f = map(int, sys.stdin.readline().rstrip().split())
edges = deque()
for _ in range(m):
a, b, c, t = map(int, sys.stdin.readline().rstrip().split())
edges.append([a, b, c, t])
left, right = 0, sys.maxsize
for _ in range(500):
parents = [i for i in range(n+1)]
mid = (left + right) / 2
# 이득 x = (f-total cost) / total time
# f = x * total time + total cost
if Kruskal(mid):
left = mid
else:
right = mid
if mid < 0: print("0.0000")
else: print(f"{mid:.4f}")
Author And Source
이 문제에 관하여([백준 2126] 지진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-2126-지진
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(mid):
pq = sorted(edges, key=lambda x:(x[2]+x[3]*mid))
# 우선순위 큐로 cost + time * x 오름차순 정렬
total = 0
for edge in pq:
node1, node2, cost, time = edge
if union(node1, node2):
total += (cost + time * mid)
if total <= f: return True
# f보다 작다면 이득이 양수
else: return False
n, m, f = map(int, sys.stdin.readline().rstrip().split())
edges = deque()
for _ in range(m):
a, b, c, t = map(int, sys.stdin.readline().rstrip().split())
edges.append([a, b, c, t])
left, right = 0, sys.maxsize
for _ in range(500):
parents = [i for i in range(n+1)]
mid = (left + right) / 2
# 이득 x = (f-total cost) / total time
# f = x * total time + total cost
if Kruskal(mid):
left = mid
else:
right = mid
if mid < 0: print("0.0000")
else: print(f"{mid:.4f}")
Author And Source
이 문제에 관하여([백준 2126] 지진), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-2126-지진저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)