Pagini recente » Cod sursa (job #2382388) | Cod sursa (job #369408) | Cod sursa (job #354663) | Cod sursa (job #1865483) | Cod sursa (job #3190999)
#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;
}