레야몬
[C++] 11408번 열혈강호 5 - 최대 유량, 최소 비용 최대 유량 본문
11407번 책 구매하기 3과 비슷한 문제라서 함께 풀이됩니다.
<코드>
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
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;
// <MCMF>
// source와 sink
int S, E;
//방향 그래프
vector<int> adj[MAX_V];
// MCMF 용량과 유량, 가중치
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V], cost[MAX_V][MAX_V];
// 최대 유량과 최소 비용
int total_flow, total_cost;
// u에서 v로 가는 용량이 capa이고 비용이 c인 간선 생성
void makeEdge(int u, int v, int capa, int c) {
capacity[u][v] = capa;
cost[u][v] = c, cost[v][u] = -c;
adj[u].push_back(v);
adj[v].push_back(u);
}
void input() {
// source와 sink
S = 0, E = 801;
cin >> N >> M;
// source와 직원 연결하기
for(int i=1; i<=N; i++)
makeEdge(S, i, 1, 0);
// 직원과 일 연결하기
for(int i=1; i<=N; i++) {
int num;
cin >> num;
for(int j=0; j<num; j++) {
int w, c;
cin >> w >> c;
makeEdge(i, w + WORK, 1, c);
}
}
// 일과 sink 연결하기
for(int i=1; i<=M; i++)
makeEdge(i + WORK, E, 1, 0);
}
// 최소 비용 최대 유량 알고리즘
void MCMF() {
while(1) {
// dfs
int parent[MAX_V], dist[MAX_V];
queue<int> q;
bool inQ[MAX_V];
// 초기화
memset(parent, -1, sizeof parent);
memset(inQ, false, sizeof inQ);
fill(dist, dist+MAX_V, INF);
dist[S] = 0;
q.push(S); inQ[S] = true;
while(!q.empty()) {
int here = q.front(); q.pop(); inQ[here] = false;
for(auto there : adj[here]) {
// 더 이상 흐를 수 있는 유량이 없으면 pass
if(capacity[here][there] <= flow[here][there])
continue;
if(parent[there] == -1 || dist[there] > dist[here] + cost[here][there]) {
parent[there] = here;
dist[there] = dist[here] + cost[here][there];
if(!inQ[there]) {
q.push(there);
inQ[there] = true;
}
}
}
}
// 더 이상의 증가 경로가 없으므로 pass
if(parent[E] == -1)
break;
int amount = INF;
for(int p = E; p!=S; p = parent[p])
amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
for(int p = E; p!=S; p = parent[p]) {
flow[parent[p]][p] += amount;
flow[p][parent[p]] -= amount;
total_cost += amount * cost[parent[p]][p];
}
total_flow += amount;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
input();
//최소 비용 최대 유량 알고리즘
MCMF();
cout << total_flow << '\n' << total_cost;
return 0;
}
※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.
'알고리즘 > 백준' 카테고리의 다른 글
[C++] 13544번 수열과 쿼리 3 - 자료 구조, 정렬, 세그먼트 트리, 머지 소트 트리 (0) | 2022.11.09 |
---|---|
[C++] 13537번 수열과 쿼리 1 - 자료 구조, 정렬, 세그먼트 트리, 머지 소트 트리 (0) | 2022.11.09 |
[C++] 13263번 나무 자르기 - DP, 볼록 껍질을 이용한 최적화 (0) | 2022.11.08 |
[C++] 3033번 가장 긴 문자열 - 문자열, 해싱, 접미사 배열과 lcp 배열, 라빈-카프 (0) | 2022.11.08 |
[C++] 1605번 반복 부분문자열 - 문자열, 해싱, 접미사 배열과 lcp 배열, 라빈-카프 (0) | 2022.11.08 |
Comments