완전 중요한 간선

시간 제한1초메모리 제한256 MB

요약
방향 유량 그래프가 주어질 때, 용량을 1 줄였을 때 최대 유량도 정확히 1만큼 줄어드는 간선의 개수를 센다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, 동적 계획법
정답자
아직 제출이 없습니다

문제

방향이 있는 플로우 그래프가 주어진다. 어떤 간선의 용량을 11 줄였을 때 그래프의 최대 유량도 정확히 11 줄어든다면, 그 간선을 완전 중요한 간선이라고 부른다.

그래프가 주어졌을 때, 완전 중요한 간선의 개수를 세어라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다.

첫째 줄에 테스트 케이스의 수 KK (1≤K≤151 \le K \le 15)가 주어진다.

각 테스트 케이스의 첫째 줄에는 정점의 수 NN과 간선의 수 MM (2≤N≤3002 \le N \le 300, 2≤M≤5,0002 \le M \le 5{,}000)이 주어진다. 11번 정점이 소스(source), NN번 정점이 싱크(sink)이다.

이어지는 MM개의 줄에는 각각 세 정수 ff, tt, bb가 주어지며, 이는 정점 ff에서 정점 tt로 향하는 용량 bb (b<1000b < 1000)의 간선을 뜻한다. 모든 간선 용량의 합은 20,00020{,}000을 넘지 않는다.

출력

각 테스트 케이스마다 완전 중요한 간선의 개수를 한 줄에 하나씩 출력한다.

예제2

  1. 예제 1

    입력
    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

  2. 예제 2

    입력
    1
2 2
1 2 5
1 2 3
    예상 출력
    2