[C++] 27723번 Karl's shopping

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

---

 

26/01/12

 

 

84주차 랜덤 마라톤 H번으로 나왔던 문제다. 최대유량 문제이다.

---

 

문제 접근 방식:

 

 

문제에서 주어진 내용은 다음과 같다.

 

물품이 $N$개 주어져있고, 물품을 결제할 수 있는 수단(상품권, 쿠폰 등등, 편의상 바우처라고 하겠음)이 $M$개가 주어져 있음.

 

또한, 바우처의 금액(예를 들자면 상품권 금액)이 $B_{i}$로 주어지고, 물품의 가격이 $A_{i}$로 주어짐.

 

그리고 각 바우처가 어떤 물품을 살 수 있는지의 정보 또한 주어짐.

 

그랬을 때, 물품을 모두 살 때 드는 "현금"의 최소 비용을 문제에서는 묻고있다.

 

 

물품을 모두 살 때 드는 현금의 최소 비용은 (물건 금액의 총 합) - (바우처를 최대한 사용했을 때의 금액)과 동일하다.

 

바우처의 최대 비용은 최대 유량으로 모델링 할 수 있다.

 

왼쪽 정점들은 물건, 오른쪽 정점들은 바우처이며, Source와 Sink를 각각 물건과 바우처에 잇고 바우처와 물건 사이의 용량은 INF로, 나머지 간선의 용량들은 각각 $A_{i}, B_{i}$로 설정하면 된다.

 

이렇게 모델링 한 후에 유량 알고리즘을 돌리면 문제를 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 27723번 Karl's shopping
// 최대 유량
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define INF 2147483647

struct Edge{
    int target, capacity, flow; // 타겟, 용량, 유량
    Edge* reverse; // 역방향 간선 참조하는 포인터
    int residualCapacity() const { // 잔여 유량 계산
        return capacity - flow;
    }
    void push(int amount){ // 유량 흘리기(갱신)
        flow += amount;
        reverse->flow -= amount;
    }
};

void addEdge(int u, int v, int capacity, vector<vector<Edge*>>& graph){
    Edge* uv = new Edge(); // u에서 v로 가는 간선 포인터
    Edge* vu = new Edge(); // v에서 u로 가는 역방향 간선 포인터
    // 정방향 간선 uv 초기화
    uv->target = v;
    uv->capacity = capacity;
    uv->flow = 0;
    uv->reverse = vu;
    // 역방향 간선 vu 초기화
    vu->target = u;
    vu->capacity = 0;
    vu->flow = 0;
    vu->reverse = uv;
    // 정방향과 역방향 둘다 넣어준다.
    graph[u].push_back(uv);
    graph[v].push_back(vu);
}

int BFS(int source, int sink, vector<Edge*>& reversedPath, vector<vector<Edge*>>& graph){
    int N = graph.size();
    vector<int> visited(N, 0);
    vector<Edge*> parent(N); // 경로 역추적하기 위한 parent배열 선언.
    queue<int> Q;
    visited[source] = 1;
    Q.push(source);
    
    bool foundAugmentingPath = false;
    while (!Q.empty() && !foundAugmentingPath){
        int now = Q.front(); Q.pop();
        for (Edge* edge: graph[now]){
            int next = edge->target;
            if (!visited[next] && edge->residualCapacity() > 0){ // 방문하지 않았고, 잔여 용량이 남아있다면
                visited[next] = 1;
                parent[next] = edge;
                Q.push(next);
                if (next == sink){ // sink로 도달가능하다면
                    foundAugmentingPath = true;
                    break;
                }
            }
        }
    }
    
    if (!foundAugmentingPath){
        return 0; // 더 이상 흘릴 유량이 없다.
    }

    reversedPath.clear();
    int Flow = INF;
    // 역방향 간선타고 가면서 흘릴 Flow 갱신
    for (Edge* edge = parent[sink]; edge != nullptr; edge = parent[edge->reverse->target]){
        Flow = min(Flow, edge->residualCapacity());
        reversedPath.push_back(edge);
    }
    return Flow;
}

int EdmondKarp(int source, int sink, vector<vector<Edge*>>& graph){
    int totalFlow = 0;
    vector<Edge*> reversedPath;
    while (int flow = BFS(source, sink, reversedPath, graph)){
        for (Edge* edge : reversedPath){
            edge->push(flow);
        }
        totalFlow += flow;
    }
    return totalFlow;
}

void solve(void){
    int N, M; cin >> N >> M;
    vector<vector<Edge*>> graph(N+M+2);
    vector<int> A(N), B(M);
    int totalCash = 0;
    for (int i = 0; i < N; ++i){
        cin >> A[i];
        totalCash += A[i];
        addEdge(0, i+1, A[i], graph);
    }
    for (int i = 0; i < M; ++i){
        cin >> B[i];
        addEdge(N+i+1, N+M+1, B[i], graph);
    }
    for (int i = 0; i < M; ++i){
        int K; cin >> K;
        int num;
        for (int j = 0; j < K; ++j){
            cin >> num;
            addEdge(num, N+i+1, INF, graph);
        }
    }
    cout << totalCash - EdmondKarp(0, N+M+1, graph) << endl;
}

int main(void){
    fastio

    int T; cin >> T;
    for (int i = 0; i < T; ++i){
        solve();
    }
    return 0;
}