jams > 문제은행

본문 바로가기


문제은행

1079 : jams

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 7 회    시도횟수: 28 회   



농장에서 소들의 마리수가 증가함에 따라 외양간으로 향하는 소의 도로에 심각한 혼잡이 발생하였다. 농부 창호는 우유를 짜는 시간대의 교통체증을 완화시키기 위해 병목지점을 찾는 방법을 만들어 보고자 했다.

 

목장은 M(1≤M≤50,000)개의 일방통행 도로을 가진 네트워크를 포함하며, 각각의 도로는 1~N까지 번호가 매겨진 N(1≤N≤5,000)개의 교차점 중 서로 다른 두 개의 교차점을 연결한다: 외양간은 N번 교차점에 있다.

 

각각의 도로는 한 교차점에서 그 교차점보다 표기숫자가 높은 교차지점으로 연결 된다.(예컨데 3->4연결은 있으나 4->3연결은 있을 수 없다.) 따라서 도로에는 사이클이 없으며 모든 길들은 외양간에 이어지게 된다.

 

한 쌍의 교차점들은 한 개 이상의 도로로 연결 될 수 있다.
우유를 짜는 혼잡한 시간대에, 소들은 그들 각각의 풀을 뜯는 장소에서 시작하여 외양간을 향해 간다.
풀 뜯는 장소들은 교차점 중에서 그 어떤 도로도 해당 교차점을 향해서 들어가지 않는 교차점들이다.
각각의 소는 '길'을 따라 움직이는데, '길'은 풀 뜯는 장소에서 외양간까지 닿는 도로의 집합이다.
임의의 한 도로를 포함하는 가장 많은 '길'의 숫자를 계산하여 농부 창호가 가장 바쁜 길(들)을 찾는 것을 돕자.

 

정답은 2^31 -1 이하이다.


첫 번째 줄에는 공백을 사이에 두고 N과 M이 주어진다. 두 번째 줄부터 M+1 번째 줄엔 공백을 간격으로 도로가 연결하는 두 교차점의 번호가 주어진다.



임의의 한 도로를 지나는 최대의 길 숫자를 출력한다.


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





USACO 2007 March Silver Cow Traffic, poj 3272

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.