보안망 차단
플래티넘 III의견: 0
어느 첩보 조직의 비밀 통신망은 \(N\) 개의 거점과, 거점들을 잇는 \(M\) 개의 양방향 통신선으로 이루어져 있다. 통신선 \((u, v, w)\) 를 끊으려면 비용 \(w\) 가 든다. 같은 두 거점 사이에 통신선이 여러 개 있을 수 있고, 각각 독립적으로 끊을 수 있다.
적의 본부 거점 \(S\) 와 아군 거점 \(T\) 가 서로 어떤 경로로도 연결되지 않도록 통신선들을 끊으려 한다. 이때 필요한 최소 총비용을 구하여라. 이미 \(S\) 와 \(T\) 가 연결되어 있지 않다면 비용은 \(0\) 이다.
- \(2 \le N \le 500\)
- \(0 \le M \le 2500\)
- \(1 \le u,v \le N\), \(u \ne v\)
- \(1 \le w \le 10^6\)
- \(1 \le S,T \le N\), \(S \ne T\)
첫 줄에 거점 수 \(N\), 통신선 수 \(M\), 두 거점 \(S\), \(T\) 가 주어진다.
이어지는 \(M\) 개의 줄에 통신선 \(u\ v\ w\) 가 주어진다(양방향).
\(S\) 와 \(T\) 를 분리하는 데 드는 최소 총비용을 정수 한 줄로 출력한다.
4 5 1 4
1 2 3
1 3 2
2 4 2
3 4 3
2 3 1
5거점 1에 붙은 통신선 \(\{(1,2,3),(1,3,2)\}\) 를 모두 끊으면 비용 \(5\) 로 1을 고립시킬 수 있다. 더 적은 비용의 분리 방법은 없으므로 최소 비용은 \(4\) 이다(최소 컷).
4 2 1 4
1 2 5
3 4 5
0\(1\) 과 \(4\) 는 처음부터 연결되어 있지 않으므로 아무 통신선도 끊을 필요가 없다. 비용은 \(0\) 이다.
다이아몬드 IIIriseoj 작성
출처 Original
평가 및 의견
보안망 차단
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
보안망 차단