[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;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.