https://www.acmicpc.net/problem/30206 30206번: 차량 배치 첫 번째 줄에 지점의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 200\,000;$ $N-1 \le M \le \min(\frac{N(N-1)}{2}, 200\,000))$ 이후 $M$개의 줄에 걸쳐 각 도로가 잇는 서로 다른 www.acmicpc.net 경우의 수 구하기 조건과 설명만 읽고 복잡해보일 수 있지만, 사실 뜯어보면 간단하기 그지없는 문제이다. 모든 연결은 가중치 1을 갖기 때문에 BFS로 1번 도로와의 거리를 구할 수 있다. 1번 도로까지의 거리를 깊이 라고 하자. 어떤 도로에서도 충돌이 일어나면 안되기 때문에, 깊이가 같은 도로가 두 개 이상이..
'차량 배치' 태그의 글 목록