하한이 있는 유량의 실현 가능성
다이아몬드 IV의견: 0
정점 \(N\)개와 방향 간선 \(M\)개로 이루어진 유량 네트워크가 있다. 각 간선 \(i\)는 시작 정점 \(u_i\), 끝 정점 \(v_i\), 그리고 그 간선을 흐르는 유량이 반드시 만족해야 하는 하한 \(l_i\)와 상한 \(r_i\) (\(l_i \le r_i\))를 가진다.
발원지 \(S\)에서 흘러나와 도착지 \(T\)로 들어가는 총 유량이 정확히 \(F\)가 되고, \(S\)와 \(T\)를 제외한 모든 정점에서 유입량과 유출량이 같으며, 모든 간선의 유량이 \([l_i, r_i]\) 범위 안에 드는 정수 유량 배정이 존재하는지 판별하여라.
\(2 \le N \le 200\)
\(1 \le M \le 2{,}000\)
\(1 \le S, T \le N\), \(S \ne T\)
\(0 \le l_i \le r_i \le 10^6\)
\(0 \le F \le 10^9\)
첫 줄에 \(N\), \(M\), \(S\), \(T\), \(F\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 각각 \(u_i\), \(v_i\), \(l_i\), \(r_i\)가 주어진다. 정점 번호는 \(1\)부터 \(N\)까지이다.
유량 배정이 존재하면 YES, 존재하지 않으면 NO를 한 줄에 출력한다.
3 3 1 3 2
1 2 1 3
2 3 1 3
1 3 0 2
YESS=1, T=3, F=2. 간선 1->2에 1, 2->3에 1, 1->3에 1을 흘리면 각 하한을 만족하고 1에서 총 2가 나가 3으로 2가 들어오므로 가능하다.
3 2 1 3 1
1 2 2 2
2 3 2 2
NO간선 하한이 모두 2라서 경로에 2가 흘러야 하는데 요구 유량 \(F=1\)과 모순되어 유량 보존을 만족할 수 없다. 따라서 NO.
riseoj 작성
출처 Original
평가 및 의견
하한이 있는 유량의 실현 가능성
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
하한이 있는 유량의 실현 가능성