문제
한국 돔 구장 건설현장에서는 인부들을 이동할 수 있게 하기 위해 가교를 설치했다.
문제는, 어떤 가교는 충분히 넓어서 양방향으로 다닐 수 있지만, 어떤 가교는 너무 좁아 한쪽으로만 갈 수 있는 가교가 있다. 현장소장인 당신은 가교들의 설치 현황을 알고 있고, 인부들의 시작지와 목적지를 이미 알고있다.
각각의 인부가 목적지로 도착하기 위해 한쪽으로만 이동할 수 있는 가교를 더 넓은 양방향 가교로 최소한으로 교체하는 방법을 구하자
입력
첫 줄에 건설현장 지점 N과 가교의 수 M이 주어진다. (3≤N≤200, N-1≤M≤N*(N-1)/2)
M+1 줄 까지 가교가 설치된 시작지 P, 도착지 Q와 해당 가교가 한쪽으로만 갈 수 있는 가교인지, 양방향으로 움직일 수 있는 가교인지 여부 B(0: 한쪽으로만 갈 수 있는 가교,1 : 양방향 가교)가 주어진다. 한 쪽으로만 움직일 수 있는 가교의 경우 시작지 P에서 Q로는 갈 수 있지만 Q에서 P로는 이동할 수 없다.
M+2 줄에는 고용할 수 있는 인부의 숫자 K가 주어진다. (1≤K≤400)
다음 K 줄에는 각각의 인부가 일할 시작지와 목적지가 주어진다.
출력
K줄에 거쳐 각각의 인부가 일할 수 있도록 교체해야 하는 가교의 수를 출력한다.
예제
4 3
1 2 0
2 3 1
3 4 0
3
1 3
1 4
3 1
0
0
1
출처
2015 연세대학교 교내 프로그래밍 대회
로그인해야 코드를 작성할 수 있어요.