레야몬

11407번 책 구매하기 3과 비슷한 문제라서 함께 풀이됩니다. #include #include #include #include using namespace std; const int INF = 987654321; const int MAX_N = 400; const int MAX_M = 400; const int MAX_V = 803; const int MAX_FLOW = 400; const int WORK = 400; // 직원의 수 N명, 해야 할 일 M개 int N, M; // // source와 sink int S, E; //방향 그래프 vector adj[MAX_V]; // MCMF 용량과 유량, 가중치 int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V], cos..

1. 문제 N명의 사람이 책을 구매하려고 한다. 각 사람은 1~N번까지 번호가 매겨져 있고 각 사람이 사려고 하는 책의 개수는 Ai권이다. 이 책을 판매하는 온라인 서점은 M개가 있고 1~M번까지 번호가 매겨져 있으며, 각 서점이 가지고 있는 책의 개수는 Bi권이다. 서점에서 가지고 있는 책의 개수의 합과 사람들이 사고자 하는 책의 개수의 합은 같다. 한 사람이 같은 서점에서 구매할 수 있는 책의 최대 개수는 Cij이다. 온라인 수점에서 책을 한 권씩만 보낼 때 배송비는 Dij원이다. 살 수 있는 책의 최대 권 수와 그 때 배송비의 합의 최솟값을 구하는 프로그램을 작성하시오. -1- 사람의 수 N, 온라인 서점의 수 M \(M(1 \leq N, M \leq 100)\) -2- 사람이 사려고 하는 책의 개..

1. 문제 강호네 회사는 직원이 N명, 해야 할 일이 M개가 있다. 직원은 1~N번, 일은 1~M번으로 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 직원은 1명이다. 단 N명 중에 K명은 일을 2개 할 수 있다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. -1- 직원의 수 N, 일의 개수 M, 일을 2개 할 수 있는 직원의 수 K \((1 \leq N, M \leq 1000, 1 \leq K \leq N)\) -N개- i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. 강호네 회사에서 할 수 있는 일의 개수를 출력하라. 2. 재정의 N명 중 K명은 2개, ..

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. 해결 방법 최대 유량 최소 컷 정리에 따라 최소컷은 최대 유량과 같다. 따라서 최대 유량 알고리즘을 ..

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다. 1. 문제 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq..

도시 왕복하기 2를 풀면서 같이 푼 문제라서 함께 풀이합니다. 1. 문제 도시 왕복하기 2: N개의 도시가 P개의 양방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 방문한 도시는 두 번 이상 방문할 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. 도시 왕복하기 1: N개의 도시가 P개의 방향 길로 연결되어 있다. 1번 도시와 2번 도시 사이에는 길이 없을 때 이석원은 1번 도시와 2번 도시를 최대한 많이 왔다 갔다 하는데 한 번 지난 길은 다시 지날 수 없다. 이때 왔다 갔다 할 수 있는 최대 횟수를 구하여라. -1- \(N(3 \leq N \leq 400)\), \(P(1 \leq P \leq..