#include using namespace std; struct Edge; typedef vector::iterator EdgeIter; struct Edge { int to, cap, flow; bool is_real; pair part; EdgeIter partner; int residual() const { return cap - flow; } }; struct Graph { vector > nbr; int num_nodes; Graph(int n) : nbr(n), num_nodes(n) { } // No check for duplicate edges! // Add (or remove) any parameters that matter for your problem void add_edge_directed(int u, int v, int cap, int flow, bool is_real, pair part) { Edge e = {v,cap,flow,is_real, part}; nbr[u].push_back(e); } }; void add_edge(Graph& G,int u,int v,int cap){ int U = G.nbr[u].size(), V = G.nbr[v].size(); G.add_edge_directed(u,v,cap,0,true ,make_pair(v,V)); G.add_edge_directed(v,u,0 ,0,false,make_pair(u,U)); } void push_path(Graph& G, int s, int t, const vector& path, int flow) { for (int i = 0; s != t; s = path[i++]->to) if (path[i]->is_real) { path[i]->flow += flow; path[i]->partner->cap += flow; } else { path[i]->cap -= flow; path[i]->partner->flow -= flow; } } int augmenting_path(Graph& G, int s, int t, vector& path, vector& visited, int step = 0) { if (s == t) return -1; visited[s] = true; for (EdgeIter it = G.nbr[s].begin(); it != G.nbr[s].end(); ++it) { int v = it->to; if (it->residual() > 0 && !visited[v]) { path[step] = it; int flow = augmenting_path(G, v, t, path, visited, step+1); if (flow == -1) return it->residual(); else if (flow > 0) return min(flow, it->residual()); } } return 0; } int network_flow(Graph& G, int s, int t) { // note that the graph is modified for(int i=0;ipart.first][it->part.second].partner = it; vector path(G.num_nodes); int flow = 0, f; do { vector visited(G.num_nodes, false); if ((f = augmenting_path(G, s, t, path, visited)) > 0) { push_path(G, s, t, path, f); flow += f; } } while (f > 0); return flow; } int main() { int N; cin >> N; Graph G(N+2); int s = N, t = N+1; const int INF = INT_MAX; int sum = 0; for (int i = 0; i < N; i++) { int v, c, m; cin >> v >> c >> m; for (int j = 0; j < m; j++) { int x; cin >> x; x--; add_edge(G, x, i, INF); } if (v-c >= 0) { sum += v-c; add_edge(G, s, i, v-c); } else { add_edge(G, i, t, c-v); } } int f = network_flow(G, s, t); cout << sum - f << endl; return 0; }