Cod sursa(job #3190999)

Utilizator AndreiKatsukiAndrei Dogarel AndreiKatsuki Data 8 ianuarie 2024 16:16:02
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("negot.in");
ofstream fout("negot.out");

const int NMAX = 1e3 + 5, MMAX = 4e4 + 5;
int n, m, k;
vector<vector<int>> Graph;
vector<int> parent;
vector<unordered_map<int, int>> capacity, flux;
vector<bool> viz;

bool bfs(int s, int t){
    fill(viz.begin(), viz.end(), false);
    queue<int> q;
    viz[s] = 1;
    q.push(s);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node == t){
            break;
        }
        for(auto it : Graph[node]){
            if(!viz[it] && capacity[node][it] > flux[node][it]){
                viz[it] = 1;
                parent[it] = node;
                q.push(it);
            }
        }
    }
    return viz[t];
}

int maxFlow(int s, int t){
    int flow = 0;
    while(bfs(s, t)){
        for(auto it : Graph[t]){
            if(viz[it] && capacity[it][t] != flux[it][t]){
                int node = t, currFlux = INT_MAX;
                parent[t] = it;
                while(node != s){
                    int prev = parent[node];
                    currFlux = min(currFlux, capacity[prev][node] - flux[prev][node]);
                    node = prev;
                }
                if(currFlux == 0){
                    continue;
                }
                node = t;
                while(node != s){
                    int prev = parent[node];
                    flux[prev][node] += currFlux;
                    flux[node][prev] -= currFlux;
                    node = prev;
                }
                flow += currFlux;
            }
        }
    }
    return flow;
}

int main(){
    fin >> n >> m >> k;
    int s = 0, t = m + n + 1;
    Graph.resize(t + 1);
    parent.resize(t + 1, -1);
    capacity.resize(t + 1);
    flux.resize(t + 1);
    viz.resize(t + 1);
    for(int i = 1; i <= n; ++i){
        int x;
        fin >> x;
        for(int j = 1; j <= x; ++j){
            int y;
            fin >> y;
            capacity[i][n + y] = INT_MAX;
            Graph[i].push_back(n + y);
            Graph[n + y].push_back(i);
        }
        capacity[s][i] = k;
        Graph[i].push_back(s);
        Graph[s].push_back(i);
    }
    for(int i = 1; i <= m; ++i){;
        capacity[n + i][t] = 1;
        Graph[n + i].push_back(t);
        Graph[t].push_back(n + i);
    }
    fout << maxFlow(s, t);
    return 0;
}