백준 11408번: 열혈강호 5 (C++)

https://www.acmicpc.net/problem/11408

11408번: 열혈강호 5

---

Solved By: MCMF, Bipartite Matching

 

{SOURCE -> people -> works -> SINK} 순서로 네트워크 모델링을 해주고, people과 works 사이의 edge에 가중치를 월급으로 두고, 모든 edge에 capacity는 1로 주어 Biparitie Matching을 하게 한 다음에 MCMF를 돌리면 풀리는 문제입니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 803
#define SOURCE 1
#define SINK 2
#define pii pair<int, int>
#define INF 1e9
using namespace std;

vector<int> adj[MAX];
int c[MAX][MAX], f[MAX][MAX];
int cost[MAX][MAX];
int n, m;

pii MCMF(int source, int sink){
    int maxflow = 0, mincost = 0;
    while(1){
        queue<int> q;
        bool isinQ[MAX];
        int parent[MAX], dist[MAX];
        fill(parent, parent + MAX, -1);
        fill(dist, dist + MAX, INF);
        
        q.push(source);
        isinQ[source] = true;
        dist[source] = 0;
        
        while(!q.empty()){
            int now = q.front(); q.pop();
            isinQ[now] = false;
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0
                && dist[now] + cost[now][next] < dist[next]){
                    dist[next] = dist[now] + cost[now][next];
                    parent[next] = now;
                    
                    if(!isinQ[next]){
                        isinQ[next] = true;
                        q.push(next);
                    }
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int tempflow = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            tempflow = min(tempflow, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            mincost += cost[parent[i]][i] * tempflow;
            
            f[parent[i]][i] += tempflow;
            f[i][parent[i]] -= tempflow;
        }
        
        maxflow += tempflow;
    }
    
    return {maxflow, mincost};
}

int main(){
    cin >> n >> m;
    
    // network modeling
    
    // 3 ~ n + 2 == people
    // n + 3 ~ n + m + 2 == work
    for(int i = 3; i <= n + 2; i++){
        int v; cin >> v;
        for(int j = 0; j < v; j++){
            int u, cv; cin >> u >> cv;
            
            adj[i].push_back(u + n + 2);
            adj[u + n + 2].push_back(i);
            
            cost[i][u + n + 2] = cv;
            cost[u + n + 2][i] = -cv;
            
            c[i][u + n + 2] = 1; // bipartite matching
        }
    }
    
    for(int i = 3; i <= n + 2; i++){
        adj[SOURCE].push_back(i);
        adj[i].push_back(SOURCE);
        c[SOURCE][i] = 1;
    }
    
    for(int i = n + 3; i <= n + m + 2; i++){
        adj[i].push_back(SINK);
        adj[SINK].push_back(i);
        c[i][SINK] = 1;
    }
    
    pii result = MCMF(SOURCE, SINK);
    cout << result.first << '\n' << result.second;
    return 0;
}