백준 11378번 열혈강호 4 - C++(cpp) 풀이

---

 

1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다.
2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다.
3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다.

 

1. 각 직원은 한 개의 일만 할 수 있으므로 각 간선의 용량이 1인 네트워크 플로우 문제로 생각할 수 있다.

 

2. 벌점을 받으면 추가로 일을 할 수 있고, 벌점의 합이 K이므로 source에서 시작해 K만큼의 용량을 각 직원에게 분산하는 정점과 간선을 추가한다.

 

3. 포드 풀커슨 알고리즘을 사용하여 최대 유량을 구한다.

 포드 풀커슨 알고리즘의 시간 복잡도는 O((V + E) * F). 최대 간선의 수가 대략 NM개(10^6)이고 최대 유량은 M(10^3)이므로 총 연산 횟수는 대략 10^9가 된다. 시간제한이 3초로 넉넉하기 때문에 10^9로도 AC를 받았다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

const int INF = 987654321;
const int MAX_V = 2005;
int N, M, K, SRC, P, SINK;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];
int parent[MAX_V];

void DFS(int here) {
    if (parent[SINK] != -1) return;
    
    for (int there = 0; there <= SINK; there++) {
        if (capacity[here][there] - flow[here][there] > 0 && parent[there] == -1) {
            parent[there] = here;
            DFS(there);
        }
    }
}

int Ford_Fulkerson() {
    int total_flow = 0;
    
    while (true) {
        memset(parent, -1, sizeof(parent));
        
        parent[SRC] = SRC;
        DFS(SRC);
        
        if (parent[SINK] == -1) break;
        
        int amount = INF;
        
        for (int p = SINK; p != SRC; p = parent[p]) {
            amount = min(amount, capacity[parent[p]][p] - flow[parent[p]][p]);
        }
        
        for (int p = SINK; p != SRC; p = parent[p]) {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        
        total_flow += amount;
    }
    
    return total_flow;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> K;
    
    SRC = N + M + 1;
    SINK = N + M + 2;
    
    capacity[SRC][P] = K;
    
    int cnt, work;
    
    for (int person=1; person<=N; person++) {
        cin >> cnt;
        
        for (int i=0; i<cnt; i++) {
            cin >> work;
            work += N;
            capacity[person][work] = 1;
        }
        
        capacity[P][person] = K;
        capacity[SRC][person] = 1;
    }
    
    for (int work=N+1; work<=N+M; work++) {
        capacity[work][SINK] = 1;
    }
    
    cout << Ford_Fulkerson();

    return 0;
}