테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 난개발 ======

===== 풀이 =====
  * 뭔가 그래프 문제처럼도 보이고 기하 문제처럼도 보이게 포장을 살짝 해놓았는데, 포장을 풀고 나면 결국 가장 인터벌이 많이 겹치는 점을 찾는 문제이다. 장소들의 x좌표는 문제를 푸는데 있어서는 무시해도 되고 y좌표만을 가지고서 1차원 배열로 생각하면 된다.
  * 각 도로들은, 도로가 연결하는 두 장소의 번호를 좌표로 변환하고 거기에서 y좌표값만들을 취하면, 가중치가 있는 1차원 구간으로 변환된다. 이제 여기에서 [[ps:Maximum Overlapping Intervals]] 를 가중치를 고려해서 구하면 된다. 시간복잡도는 O(mlogm)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 19584. 난개발".

- Problem link: https://www.acmicpc.net/problem/19584
- Solution link: http://www.teferi.net/ps/problems/boj/19584

Tags: [sweeping]
"""

import sys

ADD = 1
REMOVE = 2


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    y_coords = []
    for _ in range(N):
        # pylint: disable=unused-variable
        x, y = [int(x) for x in sys.stdin.readline().split()]
        y_coords.append(y)
    events = []
    for _ in range(M):
        u, v, c = [int(x) for x in sys.stdin.readline().split()]
        y1, y2 = y_coords[u - 1], y_coords[v - 1]
        events.append((min(y1, y2), ADD, c))
        events.append((max(y1, y2), REMOVE, -c))

    answer = 0
    traffic = 0
    for _, _, traffic_delta in sorted(events):
        traffic += traffic_delta
        answer = max(answer, traffic)

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}