11377 열혈강호3

#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<vector<int> > adj(2020);
 
int flow[2020][2020] = { 0 };
int cost[2020][2020] = { 0 };
int mid = 2010, last = 2015;
 
int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
 
    for (int i = 1; i <= n; i++) {
        int len;
        scanf("%d", &len);
 
        for (int j = 1; j <= len; j++) {
            int tmp;
            scanf("%d", &tmp);
 
            adj[i].push_back(tmp + 1000);
            adj[tmp + 1000].push_back(i);
            cost[i][tmp + 1000] = 2;
        }
    }
 
    // 노드들 연결하기. 시작부분
    for (int i = 1; i <= n; i++) {
        adj[0].push_back(i);
        adj[i].push_back(0);
        cost[0][i] = 1;
 
        adj[mid].push_back(i);
        adj[i].push_back(mid);
        cost[mid][i] = 1;
    }
    adj[0].push_back(mid);
    adj[mid].push_back(0);
    cost[0][mid] = k;
 
    // 노드들 연결하기. 끝부분
    for (int i = 1000 + 1; i <= 1000 + m; i++) {
        adj[i].push_back(last);
        adj[last].push_back(i);
        cost[i][last] = 1;
    }
 
    // 핵심 파트.
    int rst = 0;
    while (1) {
        queue<int> q;
        int visit[2020] = { 0 };
        int prev[2020] = { 0 };
 
        q.push(0);
        visit[0] = 1;
 
        int flag = 0;
        while (q.empty() == false) {
            int cur = q.front();
            q.pop();
 
            if (cur == last) {
                flag = 1;
                break;
            }
 
            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
                if (cost[cur][next] > flow[cur][next] && visit[next] == 0) {
                    visit[next] = 1;
                    prev[next] = cur;
                    q.push(next);
                }
            }
        }
 
        if (flag == 0)
            break;
 
        int end = last;
        int cur = prev[end];
        int minFlow = cost[cur][end] - flow[cur][end];
        while (cur != 0) {
            cur = prev[cur];
            end = prev[end];
 
            minFlow = min(minFlow, cost[cur][end] - flow[cur][end]);
        }
 
        end = last;
        cur = prev[end];
        flow[cur][end] += minFlow;
        flow[end][cur] -= minFlow;
        while (1) {
            cur = prev[cur];
            end = prev[end];
            flow[cur][end] += minFlow;
            flow[end][cur] -= minFlow;
 
            if (cur == 0)
                break;
        }
        rst++;
    }
 
    printf("%d", rst);
}