[c++] 백준 열혈강호 시리즈 with Network flow (190906)

열혈강호 https://www.acmicpc.net/problem/11375

열혈강호 2 https://www.acmicpc.net/problem/11376

열혈강호 3 https://www.acmicpc.net/problem/11377

열혈강호 4 https://www.acmicpc.net/problem/11378

열혈강호 5 https://www.acmicpc.net/problem/11408

열혈강호 6 https://www.acmicpc.net/problem/11409

 

Network flow 관련 시리즈 문제이다. 공부하면서 한번에 6문제를 거저먹는 나름의 꿀문제..?이다.

회사 직원이 있고, 일이 있고 한 회사 직원이 하나 혹은 그 이상의 일을 맡고, 하나의 일을 여러명이 맡는 것도 가능한 그런 느낌이다. 역방향 간선도 고려해서 그래프를 만들어줘야하고 cost도 설정해주어야 한다. 코드는 종만북에 있던  포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm) 코드를 거의 그대로 썼다.

5, 6번의 경우 단순히 방문했던 지점을 안방문하는 것이 아니라 edge가 최솟값/혹은 최댓값인지 확인하는 과정이 필요하다. 그리고 시간초과를 조심해야한다. 흐르는 유량은 augmenting path가 존재하면 무조건 1이므로 무의미한 계산과정은 빼도 된다.

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define pb push_back
#define MAX_V 2010

int V;
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V], cost[MAX_V][MAX_V];
vector<int> graph[MAX_V];
// capacity[u][v] = u에서 v로 보낼 수 있는 용량
// flow[u][v] = u에서 v로 흘러가는 유량(반대방향인 경우 음수)

// flow[][]를 계산하고 총 유량을 반환한다
int networkFlow(int source, int sink){
    // flow = 0
    memset(flow, 0, sizeof(flow)); 
    int totalFlow = 0;
    int totalCost = 0;
    while(true){
        // bfs 식으로 augmenting path 찾기
        vector<int> parent(MAX_V, -1);
        vector<int> c(MAX_V, -INF);
        vector<bool> inQueue(MAX_V, false);
        queue<int> q;
        parent[source] = source;
        c[source] = 0;
        q.push(source);
        while(!q.empty()){
            int here = q.front(); q.pop();
            inQueue[here] = false; // queue에서 제거
            for(auto there : graph[here]){
                // 최소 거리 기준을 추가해줌
                if(capacity[here][there] - flow[here][there] > 0 && c[there] < cost[here][there] + c[here]){ 
                    c[there] = cost[here][there] + c[here];
                    parent[there] = here;
                    if (!inQueue[there]){ // 현재 queue에 저장된 점이라면 queue에 저장하지 않는다
                        inQueue[there] = true;
                        q.push(there);
                        
                        if(there == sink) break;
                    }
                }
            }
        }
        // augmenting path가 없음(sink에 연결 불가능)
        if (parent[sink] == -1) break;

        // 어차피 path있으면 amount = 1이므로 amount가 중요하지 않다.
        // sink에서부터 source로 올라간다.
        for(int p = sink; p!= source; p = parent[p]){
            totalCost += cost[parent[p]][p];
            flow[parent[p]][p]++;
            flow[p][parent[p]]--;
        }
        totalFlow++;
    }
    cout << totalFlow << '\n';
    return totalCost;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    V = N+M+1;
    // source is 0번
    // sink is N+M+1
    for(int i=1; i<=N;i++){
        capacity[0][i] = 1;

        graph[0].pb(i);
        graph[i].pb(0);
        
        int n; cin >> n;
        while(n--){
            int v, c; cin >> v >> c;
            capacity[i][N+v] = 1;
            cost[i][N+v] = c;
            cost[N+v][i] = -c;

            capacity[N+v][N+M+1] = 1;
            
            graph[i].pb(N+v);
            graph[N+v].pb(i);
            
            graph[N+v].pb(N+M+1);
            graph[N+M+1].pb(N+v);
        }
    }
    cout << networkFlow(0, N+M+1) << '\n';
    return 0;
}