레야몬

1. 문제 한 중간 지점에서 두 전함이 겹치지 않는 뱃길과 중간지점을 택해 목적지에 도달한다. 중간 지점과 중간 지점 사이에는 사용해야 하는 포탄의 수가 정해져 있을 때 사용해야 하는 포탄의 최소 수를 구하시오. 2. 재정의 서로 겹치지 않는 두 경로의 가중치 합의 최솟값을 구하시오. 3. 해결방법 용량을 2로 설정하면 두 개의 경로가 만들어 지며 bfs로 최단 경로를 탐색하면 된다. #include #include #include #include #define pii pair #define fi first using namespace std; const int INF = 987654321; const int MAX_V = 2003; const int OUT = 1000; //간선 구조체 struct E..

1. 문제 N*M 크기의 도시는 빈칸 또는 벽이다. 도현이와 학교는 빈칸에 있고 도현이는 상하좌우로 인접한 칸으로 이동해 학교에 가려고 한다. 이때, 벽이 있는 칸으로는 이동할 수 없고, 도시를 벗어날 수 없을 때 도현이가 학교에 가지 못하게 빈칸을 벽으로 바꾸려고 한다. 도현이와 학교가 있는 곳은 벽으로 바꿀 수 없을 때 바꿔야 하는 횟수의 최솟값을 구하시오. -1- 도시의 세로 크기 N, 가로 크기 M \(M(1 \leq N, M \leq 100)\) M개의 줄 도시의 모양이 주어진다. 빈칸: '.', 벽: '#', 도현이의 위치: 'K', 학교의 위치: 'H'. K와 H는 하나만 주어진다. 바뀌는 벽의 최솟값을 출력하라. 만약 벽을 세워도 막을 수 없다면 -1을 출력하라. 2. 재정의 바뀌는 벽의 ..

1. 문제 정점 n개, 간선 m개로 이루어진 가중치가 있는 무방향 그래프가 주어진다. 특정 정점 s, t가 비연결되도록 간선을 제거하는데, 제거한 간선의 가중치의 합의 최솟값을 구하시오. -1- 정점의 개수 n, 간선의 수 m이 주어짐 \((2 \leq n \leq 500, 1 \leq m \leq 10,000)\) m줄 a와 b사이 가중치 c \((1 \leq a, b \leq n, 1 \leq c \leq 100, a \neq b)\) -m+2- 두 정점 s, t \((1 \leq s, t \leq n, s \neq t)\) 제거한 간선의 가중치 합의 최솟값 출력 2. 재정의 최소컷을 구하시오. 3. 해결 방법 최대 유량 최소 컷 정리에 따라 최소컷은 최대 유량과 같다. 따라서 최대 유량 알고리즘을 ..