[BOJ 5651] 완전 중요한 간선

문제 출처 : https://www.acmicpc.net/problem/5651

5651번: 완전 중요한 간선

 

풀이 :

네트워크 플로우 최대 유량 문제입니다.

 

Source는 1번 정점, Sink는 N번 정점으로

엣지중 Capacity가 1 줄었을때 Maximum Flow도 1이 줄어드는 간선의 개수를 찾는 문제입니다.

 

우선 Maximum Flow를 구해 준 다음

 

Capacity와 Flow의 차이가 0 즉 최대로 흐르고 있는 엣지에 대해

엣지의 시작지점에서 엣지의 도착지점까지 흐를수 있는 다른 경로가 있는지를 탐색한 후

다른 경로가 있으면 완전 중요한 간선이 아니고,

다른 경로가 없으면 완전 중요한 간선이 됩니다.

 

그 이유는 다른 증가경로가 있다면 현재 선택된 엣지를 타지 않고도 충분히 Maximum Flow만큼 흘릴 수 있기 때문입니다.