# 디니츠 알고리즘 코드 (C++)

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
const int MAX_V = 502;
const int INF = 987654321;
const int FOOD = 250;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int work[MAX_V];
int level[MAX_V];
 
 
vector<int> adj[502];
 
int S = 0, T = 500;
 
 
// 디닉 bfs (수행시간 - O(E)) / level graph 생성
bool bfs()
{
    fill(level, level + MAX_V, -1);
 
    level[S] = 0;
 
    queue<int> q;
 
    // source 삽입
    q.push(S)
 
    // edge만큼 반복
    while (!q.empty())
    {
        int here = q.front();
        q.pop();
 
        // 인접 edge 탐색
        for (int i = 0; i < adj[here].size(); i++)
        {
            int next = adj[here][i];
 
            // flow가 흐를 수 있는지 확인
            if (level[next] == -1 && c[here][next] - f[here][next] > 0)
            {
                level[next] = level[here] + 1;
                q.push(next);
            }
        }
    }
 
    return level[T] != -1;
}
 
// 디닉 dfs (수행시간 - O(VE)) / 차단유량
int dfs(int here, int flow)
{
    // sink에 도착
    if (here == T)
        return flow;
 
    // edge만큼 반복
    for (int &i = work[here]; i < adj[here].size(); i++)
    {
        int next = adj[here][i];
 
        // flow가 흐를 수 있는지 확인
        if (level[next] == level[here] + 1 && c[here][next] - f[here][next] > 0)
        {
            // vertex만큼 dfs 수행
            int ret = dfs(next, min(c[here][next] - f[here][next], flow));
 
            // flow 업데이트
            if (ret > 0)
            {
                f[here][next] += ret;
                f[next][here] -= ret;
 
                return ret;
            }
        }
    }
 
    return 0;
}
 
int main()
{
    int n, k, d;
    cin >> n >> k >> d;
 
    for (int i = 1; i <= n; i++)
    {
        c[S][i] = k;
 
        adj[S].push_back(i);
        adj[i].push_back(S);
    }
 
    for (int i = 1; i <= d; i++)
    {
        int val;
        cin >> val;
 
        c[i + FOOD][T] = val;
        adj[i + FOOD].push_back(T);
        adj[T].push_back(i + FOOD);
    }
 
    for (int i = 1; i <= n; i++)
    {
        int cnt;
        cin >> cnt;
 
        for (int j = 0; j < cnt; j++)
        {
            int pos;
            cin >> pos;
 
            c[i][pos + FOOD] = 1;
 
            adj[i].push_back(pos + FOOD);
            adj[pos + FOOD].push_back(i);
        }
    }
 
 
    int totalFlow = 0;
 
    // bfs/dfs를 v만큼 반복 - O(V^2E)
    while (bfs())
    {
        fill(work, work + MAX_V, 0);
 
        while (1)
        {
            int flow = dfs(S, INF);
            if (flow == 0)
                break;
            totalFlow += flow;
        }
    }
 
    cout << totalFlow;
 
    return 0;
}


출처: https://www.crocus.co.kr/1088 [Crocus]