[BOJ 2367] 파티

문제 출처 : https://www.acmicpc.net/problem/2367

 

풀이 :

 

네트워크 플로우 (Maximum Flow) 문제입니다.

파티에 N명의 사람이 오고 D개의 음식을 준비해야하는데 한 사람당 음식을 K개 준비할 수 있고 같은 음식은 1개만 준비할 수 있습니다.

 

따라서 다음과 같이 모델링 할 수 있습니다.

 

1. Source에서 사람으로 K만큼의 Capacity를 가진 Edge를 연결

2. 사람에서 각 사람당 준비할 수 있는 음식으로 1만큼의 Capacity를 가진 Edge를 연결 (한개의 음식은 한사람당 하나만 들고갈수 있으므로)

3. 각 음식에서 Sink로 가져올 수 있는 갯수만큼의 Capacity를 가진 Edge를 연결

 

예제의 경우를 네트워크 플로우로 모델링 하면 아래와 같은 모형이 나옵니다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define ms 302
 
struct edge {
    int to, c, f;
    edge *d;
    edge(int to1,int c1):to(to1),c(c1),f(0),d(nullptr){}
    int spare() { return c - f; }
    void addFlow(int f1) {
        f += f1;
        d->f -= f1;
    }
};
 
int n, k, d, S = 0, E = 1, t, arr[100], a, mf;
vector<edge *> adj[ms];
 
void addEdge(int u, int v, int c) {
    edge *e1 = new edge(v, c), *e2 = new edge(u, 0);
    e1->d = e2;
    e2->d = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k >> d;
    for (int i = 0; i < d; i++)cin >> arr[i];
    for (int i = 2; i < n + 2; i++) {
        addEdge(S, i, k);
        cin >> t;
        for (int j = 0; j < t; j++) {
            cin >> a;
            addEdge(i, a + n + 1, 1);
        }
    }
    for (int i = n + 2; i < n + 2 + d; i++)addEdge(i, E, arr[i - n - 2]);
    while (1) {
        int pre[ms];
        for (int i = 0; i < ms; i++)pre[i] = -1;
        edge *path[ms] = { 0 };
        queue<int>q;
        q.push(S);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            for (edge *e : adj[now]) {
                int next = e->to;
                if (e->spare() > 0 && pre[next] == -1) {
                    pre[next] = now;
                    path[next] = e;
                    q.push(next);
                    if (next == E)break;
                }
            }
        }
        if (pre[E] == -1)break;
        int flow = 1e9;
        for (int i = E; i != S; i = pre[i]) flow = min(flow, path[i]->spare());
        for (int i = E; i != S; i = pre[i]) path[i]->addFlow(flow);
        mf += flow;
    }
    cout << mf;
}