톨게이트 > 문제은행

본문 바로가기


문제은행

2755 : 톨게이트

제한시간: 2Sec    메모리제한: 128mb
해결횟수: 3회    시도횟수: 52회   



어느 나라에는 N 개의 도시와 M 개의 도로로 구성된 도로망이 있다. 각 도로는 서로 다른 두 도시를 직접 잇는 형태이며, 서로 다른 두 도로가 도로의 중간에서 교차하는 일은 없다. 도로는 양방향 통행이 가능하고, 한 쌍의 도시 사이에는 최대 하나의 도로가 있다. 모든 개별 도로들의 길이는 동일하다. 또한, 도로망을 통해서 어떤 도시에서든 다른 모든 도시로 이동이 가능하다. 모든 도시의 인구수는 1 이상의 자연수이다. 각 도시에는 0개 이상의 맛집이 있다. (맛집은 유명한 음식점을 말한다.)

 

이 나라의 도로망을 조사해 보니 특이한 점을 한 가지 발견하게 되었다. 한 도시에서 출발해서 몇 개의 도로들을 따라가면 다시 원래의 도시로 돌아올 수 있는 도로들의 집합을 사이클이라고 부른다. (단, 같은 도로를 두 번 이상 사용할 수 없다.) 이 나라의 도로망의 특이한 점은 모든 개별 도로는 최대 하나의 사이클에 속한다는 것이다. 예를 들어, 아래 그림에서 원이 도시들이고 선이 도로라고 하면 각 도로들이 모두 2개의 사이클에 속하게 되므로 이 문제에서는 주어지지 않는 경우이다.

 

028844cac9ef50d1e91bc22817e783cc_1451798 

 

이 나라의 모든 사람들은 일 년 동안 모든 맛집을 한 번씩만 다녀온다. A 도시에 사는 사람이 B 도시의 맛집을 다녀온다는 것은 A에서 출발하여 B에 있는 하나의 맛집만 방문하고 A로 다시 돌아오는 것을 말한다. (즉, 그 과정에서 다른 맛집을 방문하지 않는다.) 또, A에서 B의 맛집을 다녀오는 경우 A에서 B로 가는 가장 짧은 길을 왕복한다. 가장 짧은 길이 여러 개 존재하는 경우는 동일한 확률로 그 중 하나를 선택한다.

 

이 나라의 재정이 최근 부족하여 도로들 중 단 하나에 톨게이트를 설치하려고 한다. 톨게이트를 어느 방향으로 통과하든 비용을 지불해야 하며 이동 거리에 관계없이 모두 동일한 비용을 지불한다.

 

도시의 수, 도시별 인구수와 맛집의 수, 그리고 도로망을 입력 받아 일 년 동안 가장 많은 통행료 수입을 기대할 수 있는 도로를 찾는 프로그램을 작성하라. 동일한 기댓값을 가지는 도로가 여러 개인 경우 모두 다 출력하여야 한다.

 

아래 그림의 예를 보자. 그림에서 원 안에 있는 수는 도시의 번호이며, 원 옆에 있는 두 수는 각각 도시의 인구수와 맛집의 수이다. 화살표는 1번 도시와 5번 도시 간의 가장 짧은 길의 한 예이다. 1번 도시에서 2번 도시로 가는 가장 짧은 길은 한 가지 뿐이지만, 1번 도시에서 5번 도시로 가는 가장 짧은 길은 두 가지이다. 모든 상황을 고려하면 4번 도시와 5번 도시 사이에 톨게이트를 설치하는 것이 가장 많은 통행료 수입을 기대할 수 있음을 알 수 있다.

 

028844cac9ef50d1e91bc22817e783cc_1451798 


입력파일의 첫 줄에는 도시의 수를 나타내는 정수 N 과 도로의 수를 나타내는 정수 M 이 공백을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 200,000, 2 ≤ M ≤ 300,000 이다. 도시는 1번부터 N 번 까지 번호가 붙어 있다.

둘째 줄부터 N개의 줄에는 각 도시의 인구수와 맛집의 수가 두 개의 음 아닌 정수로 공백을 사이에 두고 주어진다. 첫 번째 수가 인구수이며 두 번째 수가 맛집의 수이다. 인구수와 맛집의 수는 도시의 번호 순서대로 주어진다.

이후 M개의 줄에는 도로의 정보가 도시 번호의 쌍으로 공백을 사이에 두고 주어진다. 도시 번호의 쌍은 항상 앞 번호가 뒤 번호보다 작은 형태이다. 도시번호의 쌍들은 앞 번호가 작은 것부터 주어지며, 같은 앞 번호들 간에는 뒤 번호가 작은 것부터 주어진다.

계산 과정에서 32비트 자연수 변수가 표현할 수 있는 범위를 넘어서 64비트 자연수 변수를 사용해야 할 수도 있음에 주의하라.

<제약조건>
• 채점 데이터 중 10%에서 N ≤ 30 이다.<
• 채점 데이터 중 10%에서 도로망의 전체적인 모양이 한 직선과 같다. 즉, 도시들 중 두 개는 단 하나의 도로에만 연결되어 있으며 나머지 도시들은 각각 두 개의 도로에 연결되어 있다.
• 채점 데이터 중 20%에서 도로망에 사이클이 존재하지 않는다. (직선 모양은 아니다.)
• 채점 데이터 중 60%에서 원래의 제한 이외의 추가 제한이 없다.


여러분은 첫 줄에 톨게이트를 설치하면 통행료의 기댓값이 가장 높은 도로들의 수 K 를 출력해야 한다. 이후 K 개의 줄에 통행료의 기댓값이 가장 높은 도로들을 도시 번호의 쌍으로 공백을 사이에 두고 출력한다.

도시 번호의 쌍들을 출력하는 순서는 입력과 동일한 것을 사용해야 한다.

[Copy]
5 4
1 1
1 1
1 1
1 1
1 1
1 2
2 3
3 4
4 5
[Copy]
2
2 3
3 4


[Copy]
5 5
1 1
1 1
2 1
2 1
5 1
1 2
1 3
2 4
3 4
4 5
[Copy]
1
4 5




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.