문제
노드 $N$개, 엣지 $M$개인 그래프가 있다. 이 그래프에는 총 K마리의 드래곤이 사는데, 각 드래곤은 처음에 $S_i$개의 머리를 가지고 있으며 매 분마다 $N_i$개의 머리가 새로 생겨난다. 어떤 노드에는 여러 마리의 드래곤이 있을 수도 있고, 드래곤이 없을 수도 있다.
한편 워리어는 매 분마다 (1)드래곤의 머리 하나를 자르거나 (2) 이웃한 노드로 움직일 수 있다. 모든 드래곤을 죽일 수 있는(머리를 모두 자를 수 있는) 워리어의 최소 수를 구하는 문제이다.
접근
대략 생각해보면, 드래곤을 잡기 위해서는 (1)처음부터 드래곤을 기다렸다가 $S_i$명의 워리어가 1분에 머리를 자르는 방법 (2)$N_i+1$명 이상의 워리어를 고용하여 머리가 생기는 속도보다 빠르게 자르는 방법이 있을 것이다.
그렇다면 그 외에, (3)어느정도 드래곤 머리가 생기기를 기다렸다가 워리어가 모여서 처치하는 상황은 생각하지 않아도 될까? 이 부분이 사실 까다로운데, 결론만 보면 그렇다. 이는 다음과 같이 대략적으로 발견할 수 있다. (엄밀한 증명은 아니다)
초기 상태가 아닌 $t$분 후에, 어떤 드래곤의 머리 갯수 $S^t_i$는 항상 $S^t_i \ge N_i$이다(머리가 자라므로). 그렇다면 그 순간부터 드래곤을 잡기 위해서는 워리어 $x>N_i$명이 이 드래곤 앞에 모여있어야 하는데, 이는 앞에서의 (2)번 상황에 이미 포함된다. 즉, 초기 상태가 아닌 경우 드래곤을 잡기 위해서는 결국 $N_i+1$명 이상의 워리어가 필요하다.
이러한 사실을 바탕으로, 우선 $max(N_i)+1$명의 워리어가 있으면 드래곤을 잡을 수 있다는 사실을 발견할 수 있다. 또, 이로 인해 가능한 워리어 수의 범위 역시 $max(N_i)+1$ 이하이므로, $10^5+1$이하여야 함을 알 수 있다.
그렇다면 결국 워리어의 수 $w$라 할 때, $1 \le w \le 10^5+1$에 대해서 루프를 돌며 (1)번 방법으로 잡아야 하는 수보다 큰지 확인하면 된다. $N_i\lt w $인 경우는 어차피 언젠가는 잡을 수 있으므로 무시하고, $N_i\ge w $인 $i$에 대하여 $\Sigma S_i \le w$인지 확인하면 된다.
주의할 점
도로가 이 문제의 함정이다. 주어진 그래프가 연결 그래프라는 보장이 없다. 그래프를 연결요소로 분해하여 각 연결요소에 대한 부분 답을 모두 더하여 정답을 내야한다. 연결 요소에 드래곤이 한마리도 없을 수도 있다.
Code
링크# https://www.acmicpc.net/problem/10605
# Greedy - kill dragon at start(xi>Si) or by crowd(sum(xi) > max(Ni))
from bisect import *
from collections import deque
from sys import stdin
def solve(n, m, k):
graph = [[] for _ in range(n)]
for _ in range(m):
a, b = map(int, stdin.readline().split())
graph[a - 1].append(b - 1)
graph[b - 1].append(a - 1)
dragons = [[] for _ in range(n)]
for _ in range(k):
ci, si, ni = map(int, stdin.readline().split())
dragons[ci - 1].append([ni, si]) # change order for simpler implementation
ans = 0
visited = [False for _ in range(n)]
for node in range(n):
if not visited[node]:
# Make partial solution for connected component
target = dragons[node]
Q = deque([node])
visited[node] = True
while Q:
curr = Q.popleft()
for child in graph[curr]:
if not visited[child]:
visited[child] = True
target.extend(dragons[child])
Q.append(child)
if len(target) == 0: # no dragon in this connected component.
continue
target.sort() # Ni, Si
si_partial = [0 for _ in range(len(target) + 1)]
acc = 0
for i in range(len(target)):
acc += target[i][1]
si_partial[i + 1] = acc
curr_ans = 0
for hero in range(1, 10 ** 5 + 1):
start_idx = bisect_left(target, [hero, -1])
if start_idx == len(target): # num of hero exceeds sum of ni
curr_ans = hero
break
if si_partial[-1] - si_partial[start_idx] <= hero:
curr_ans = hero
break
ans += curr_ans
print(ans)
while True:
n, m, k = map(int, stdin.readline().split())
if n == m == k == 0:
break
else:
solve(n, m, k)
