시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2447 | 792 | 460 | 28.660% |
어떤 플로우 그래프가 주어졌을때, 한 간선의 용량이 1줄면 최대 유량도 1이 줄어드는 경우 그 간선을 완전 중요한 간선이라고 부른다. 그래프가 주어진 경우 완전 중요한 간선의 개수를 세어보자!
입력은 여러개의 테스트케이스로 이뤄진다. 첫째 줄에는 테스트케이스의 수 K (1<=K<=15)가 주어진다. 각 테스트 케이스에는 N, M (2 <= N <= 300; 2 <= M <= 5,000)가 주어지고 각각 정점의 수와 간선의 수를 뜻한다. 1번 정점은 source를 N번 정점은 sink를 뜻한다.
다음 M줄에 걸쳐서는 세개의 정수 f, t, b가 주어지는데 f에서 t로 가는 간선의 용량이 b(<1000)라는 뜻이다. 모든 유량의 합은 20,000을 넘지 않는다.
각 테스트케이스마다 한줄씩 완전 중요한 간선의 수를 출력한다.
3 2 3 1 2 10 1 2 5 1 2 7 4 3 1 2 10 2 3 5 3 4 6 5 7 1 2 2 1 3 3 2 3 10 3 2 10 3 4 4 2 4 2 4 5 5
3 1 3
ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest P4번