[BOJ/17222] 위스키 거래, c++

🔗 링크

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

17222번: 위스키 거래

🤯 한줄 후기

위스키는 립밤 바르듯이 먹는거임

🤷 문제

👩‍💻 풀이

최대 유량 문제이다.

명진 -> 명진 친구들 -> 주은 친구들 -> 주은

이 방향을 최대 유량을 계산해주면 된다.

주은이는 중간에 친구들 각각이 만족만하면 위스키를 무한대로 받을 수 있기 때문에 d[i][e] (e = end) = INF 로 초기화해준다.

명진이 친구들은 받을 수 있는 위스키 양 제한이 있기 때문에 d[s][i] = cnt 를 넣어주면 된다.

이제 중간 명진 친구 - 주은 친구는 주은 친구들이 받을 수 있는 위스키 양을 넣어주면 된다.

이렇게 각 간선별 흐를 수 있는 용량 (capacity)을 초기화 해준 뒤 바로 최대 유량을 구해주면 된다!

에드몬드-카프 알고리즘을 통해 구해주었다. 

최대 유량 알고리즘을 안다면 쉽게 접근할 수 있는 기본 문제이다.

💻 코드

//AC
//BOJ 17222 위스키 거래
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
#define INF 987654321
#define SIZE 220
vector<int> v[SIZE];
int c[SIZE][SIZE];
int f[SIZE][SIZE];
int maxFlow(int s, int e)
{
    int total = 0;
    while (1)
    {
        queue<int> q;
        vector<int> parent(SIZE, -1);
        q.push(s);
        while (!q.empty() && parent[s] == -1)
        {
            int cur = q.front();
            q.pop();
            for (int next : v[cur])
            {
                if (c[cur][next] - f[cur][next] > 0 && parent[next] == -1)
                {
                    q.push(next);
                    parent[next] = cur;
                }
            }
        }
        if (parent[e] == -1)
            break;
        int amount = INF;
        for (int i = e; i != s; i = parent[i])
        {
            amount = min(amount, c[parent[i]][i] - f[parent[i]][i]);
        }
        for (int i = e; i != s; i = parent[i])
        {
            f[parent[i]][i] += amount;
        }
        total += amount;
    }
    return total;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int cnt[N + M];
    int s = 0, e = N + M + 1;
    for (int i = 1; i <= N; i++)
    {
        cin >> cnt[i];
        v[e].push_back(i);
        v[i].push_back(e);
        c[i][e] = INF;
    }
    for (int i = N + 1; i <= N + M; i++)
    {
        cin >> c[s][i];
        v[i].push_back(s);
        v[s].push_back(i);
        cnt[i] = c[s][i];
    }
    for (int i = N + 1; i <= N + M; i++)
    {
        int n;
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            int node;
            cin >> node;
            v[i].push_back(node);
            v[node].push_back(i);
            c[i][node] = cnt[node];
        }
    }
    int total = maxFlow(s, e);
    cout << total;
    return 0;
}