[백준 11377] 열혈강호 3 (C++)

11377번: 열혈강호 3

최대 유량

---

최대 유량 연습하기

 

열혈 강호 1번 문제와 동일하지만 2가지 일을 할 수 있는 직원의 수가 주어진다.

처음에 무식하게 직원 중에서 k명을 반복해서 뽑고 S에서 해당 직원으로 가는 용량을 2로 두어 매번 에드몬드 카프 알고리즘을 돌려볼까 하는 생각을 했었다. 당연히 그렇게 풀면 안된다.

 

S에서 직원으로 일을 할 수 있는 에너지를 보낸다고 생각했다. 그리고 S말고 다른 정점에서 직원들에게 K만큼의 에너지를 1씩 분배해서 더 줄 수 있다면 풀 수 있다. (K에서 개별 직원에게 주는 에너지의 용량은 1) 

 

K정점을 추가하고 K정점과 S의 용량은 K, K와 직원들 사이의 용량은 1로 두고 에드몬드 카프 알고리즘을 통해 최대 유량을 구하면 된다.

 

에드몬드 카프 알고리즘에서 용량은 반드시 단방향이어야 한다.

유량을 상쇄하기 위해서 음수 flow를 흘려 보낼 수 있는데 이때 음수 flow를 처음 보냄에도 불구하고 용량이 0이 아닌 다른 값이라면 남은 용량의 값이 이상해져서 정점들을 올바르게 탐색하지 못하게 되고 최대유량을 제대로 구할 수 없다.

 

처음에 직원과 일 사이의 용량을 양방향으로 설정해서 계속 틀렸다. 많이 아쉬웠다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define MAX 2005
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, K;
int capacity[MAX][MAX], flow[MAX][MAX];
vector<int> adj[MAX];
 
void input(){
    cin >> N >> M >> K;
    int a, b;
    adj[0].push_back(2); adj[2].push_back(0);
    capacity[0][2] = K;
    for(int i = 3; i < 3+N; i++){
        cin >> a;
        adj[0].push_back(i); adj[i].push_back(0);
        adj[2].push_back(i); adj[i].push_back(2);
        capacity[0][i] = capacity[2][i] = 1;
        for(int j = 0; j < a; j++){
            cin >> b;
            adj[i].push_back(2+N+b); adj[2+N+b].push_back(i);
            capacity[i][2+N+b] = 1;
        }
    }
    for(int i = 3+N; i < 3+N+M; i++){
        adj[i].push_back(1); adj[1].push_back(i);
        capacity[i][1] = 1;
    }
}
 
void MaxFlow(int source, int sink){
    int total_flow = 0;
    
    while(true){
        vector<int> prev(MAX, -1);
        queue<int> que;
        que.push(source);
        prev[source] = source;
        
        while(!que.empty() && prev[sink] == -1){
            int now = que.front();
            que.pop();
            
            for(int k = 0; k < adj[now].size(); k++){
                int next = adj[now][k];
                if(capacity[now][next] - flow[now][next] > 0 && prev[next] == -1){
                    prev[next] = now;
                    que.push(next);
                }
            }
        }
        if(prev[sink] == -1) break;
        int amount = INF;
        for(int p = sink; p != source; p = prev[p]){
            amount = min(amount, capacity[prev[p]][p] - flow[prev[p]][p]);
        }
        for(int p = sink; p != source; p = prev[p]){
            flow[prev[p]][p] += amount;
            flow[p][prev[p]] -= amount;
        }
        total_flow += amount;
    }
    
    cout << total_flow << "\n";
}
 
int main(){
    fastio
    input();
    MaxFlow(0, 1);
    
    return 0;
}