백준 11409번: 열혈강호 6 (C++)

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

11409번: 열혈강호 6

---

Solved By: MCMF, Bipartite Matching

 

열혈강호 5 문제와 같은 문제입니다. 하지만, 이 문제에서는 주어야 하는 월급의 최솟값이 아닌 월급의 최댓값을 구합니다. 이 경우 최단 경로 알고리즘에서도 쓰이던 트릭 같은 테크닉을 이용합니다. 비용(가중치)를 음수 값으로 주어서 그대로 MCMF를 구한 것에서 mincost의 음수 값을 구하게 되면 최댓값을 구할 수 있습니다.

 

오랜만에 생각난 테크닉이라 다시금 기억에 남길 수 있었습니다.

 

#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, maxcost = 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]){
            maxcost -= cost[parent[i]][i] * tempflow;
            
            f[parent[i]][i] += tempflow;
            f[i][parent[i]] -= tempflow;
        }
        
        maxflow += tempflow;
    }
    
    return {maxflow, maxcost};
}

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