도시의 모든 절단면
다이아몬드 II의견: 0
\(N\)개의 도시와 \(M\)개의 양방향 도로로 이루어진 연결된 가중 그래프가 주어진다. \(i\)번째 도로는 두 도시 \(u_i\), \(v_i\)를 잇고 용량(가중치) \(w_i\)를 가진다.
두 도시 \(u\), \(v\) 사이의 최소 절단이란, 제거했을 때 \(u\)와 \(v\)가 더 이상 연결되지 않게 만드는 도로 집합의 가중치 합의 최솟값을 말한다. (즉 \(u\)-\(v\) 최소 컷의 용량이다.)
\(Q\)개의 질의가 주어지며, 각 질의는 두 도시 \(u\), \(v\)로 이루어진다. 각 질의에 대해 \(u\)와 \(v\) 사이의 최소 절단 값을 구하라.
질의가 최대 \(10^5\)개에 달하므로 매 질의마다 독립적으로 최소 컷을 계산하면 제한 시간을 초과한다.
\(2 \le N \le 150\)
\(N-1 \le M \le 2000\)
\(1 \le Q \le 10^5\)
\(1 \le w_i \le 10^9\)
그래프는 연결되어 있다. 같은 두 도시 사이에 여러 도로가 있을 수 있다.
첫 줄에 도시 수 \(N\), 도로 수 \(M\), 질의 수 \(Q\)가 주어진다.
이어지는 \(M\)개의 줄에 각 도로의 \(u_i\), \(v_i\), \(w_i\)가 주어진다 (\(1 \le u_i, v_i \le N\), \(u_i \ne v_i\)).
이어지는 \(Q\)개의 줄에 각 질의의 두 도시 \(u\), \(v\)가 주어진다 (\(u \ne v\)).
각 질의에 대해 \(u\)와 \(v\) 사이의 최소 절단 값을 한 줄에 하나씩 출력한다.
4 5 3
1 2 3
2 3 4
3 4 5
4 1 2
1 3 1
1 3
2 4
1 4
6
7
6도시 4개. 0-2 최소 절단, 1-3 최소 절단, 0-3 최소 절단을 각각 구한 값이다. 모든 질의의 답은 두 정점을 분리하는 최소 컷 용량과 같다.
3 2 2
1 2 7
2 3 3
1 3
1 2
3
7경로 0-1(7)-2(3). 0과 2를 분리하려면 더 작은 도로(가중치 3)를 끊는 것이 최선이므로 3. 0과 1을 분리하려면 가중치 7 도로를 끊어야 하므로 7.
riseoj 작성
출처 Original
평가 및 의견
도시의 모든 절단면
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
도시의 모든 절단면