[BOJ] 11408 : 열혈강호 5

Drakk·2021년 7월 26일

C boj mcmf 네트워크유량 백준 알고리즘 최대유량

알고리즘 문제풀이

목록 보기

14/22

💉문제 내용

문제 풀러가기

💉입출력

🧺입력
첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 400)
둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호와 그 일을 할 때 지급해야 하는 월급이 주어진다. 월급은 10,000보다 작거나 같은 자연수 또는 0이다.

🧺출력
첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.
둘째 줄에는 강호가 지급해야 하는 월급의 최솟값을 출력한다.

🔋예제 입출력

🔮예제 입력

5 5
2 1 3 2 2
1 1 5
2 2 1 3 7
3 3 9 4 9 5 9
1 1 0

🔮예제 출력
4
18

💉문제 분석

🔋분류

최대유량, 네트워크유량, 최소비용 최대유량

🔋난이도

플래티넘III

💉문제 풀이

🔋해법

최소비용 최대유량문제입니다.
이번문제는 살짝 노트해놓을 목적으로 쓴글입니다.

🔋소스코드

#include <bits/stdc++.h>

constexpr int MAX = 903;
constexpr int INF = 987654321;

constexpr int WORK = 400;
constexpr int S = MAX - 2;
constexpr int T = MAX - 1;

std::vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX], d[MAX][MAX];

void mcmf(){
	int result = 0, count = 0;
	
	while(true){
		std::vector<int> prev(MAX, -1);
		std::vector<int> dist(MAX, INF);
		std::vector<bool> inq(MAX, false);
		std::queue<int> q;
		
		q.push(S);
		dist[S] = 0;
		inq[S] = true;
		
		while(!q.empty()){
			int x = q.front();
			q.pop();
			
			inq[x] = false;
			
			for(int i=0;i<adj[x].size();++i){
				int y = adj[x][i];
				
				if(c[x][y] - f[x][y] > 0 && dist[y] > dist[x] + d[x][y]){
					dist[y] = dist[x] + d[x][y];
					prev[y] = x;
					if(!inq[y]){
						inq[y] = true;
						q.push(y);
					}
				}
			}
		}
		
		if(prev[T] == -1) break;
		
		int flow = INF;
		for(int i=T;i!=S;i=prev[i]) flow = std::min(flow, c[prev[i]][i] - f[prev[i]][i]);
		for(int i=T;i!=S;i=prev[i]){
			result += flow * d[prev[i]][i];
			f[prev[i]][i] += flow;
			f[i][prev[i]] -= flow;
		}
		++count;
	}
	
	std::cout << count << '\n' << result;
}

int main() {
	int N, M;
	
	std::cin >> N >> M;
	for(int i=1;i<=N;++i){
		adj[S].push_back(i);
		adj[i].push_back(S);
		c[S][i] = 1;
	}
	
	for(int i=1;i<=M;++i){
		adj[i + WORK].push_back(T);
		adj[T].push_back(i + WORK);
		c[i + WORK][T] = 1;
	}
	
	for(int i=1;i<=N;++i){
		int wNumber;
		std::cin >> wNumber;
		
		for(int j=0;j<wNumber;++j){
			int dst, cost;
			std::cin >> dst >> cost;
			
			adj[i].push_back(dst + WORK);
			adj[dst + WORK].push_back(i);
			
			d[i][dst + WORK] = cost;
			d[dst + WORK][i] = -cost;
			c[i][dst + WORK] = 1;
		}
	}
	
	mcmf();
}