W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1，E2， $\cdots$ ，Em}，和进行这些实验需要使用的全部仪器的集合 I={I1， I2， $\cdots $In}。 实验 Ej 需要用到的仪器是 I 的子集 Rj∈I。配置仪器 Ik 的费用为 Ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 Pj 美元。W 教授的任务是找出一个有效算法， 确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。 对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划，输出最大收益值。
输入格式
输入文件第 1 行有 2 个正整数 m 和 n（1<=m,n<=400）。其中 m 是实验数，n 是仪器数。接下来的 m 行，每行是一个实验的有关数据（每个数不超过50）。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的 n 个数是配置每个仪器的费用。
#include<bits/stdc++.h> usingnamespacestd; int n, m; int index; int e[50000][3]; int head[1005]; constint INF = 100000; bool vis[1005]; int level[1005]; inlineboolbfs(){ for (int i = 0; i <= n + m + 1; i++) vis[i] = level[i] = 0; queue<int> q; q.push(0); vis[0] = true; while (!q.empty()) { registerint cur = q.front(); q.pop(); for (int i = head[cur]; i != -1; i = e[i][1]) { int v = e[i][0]; if (!vis[v] && e[i][2] > 0) { level[v] = level[cur] + 1; if (v == n + 1 + m) returntrue; vis[v] = true; q.push(v); } } } return vis[n + 1 + m]; } intdfs(int u, int minf){ if (minf == 0 || u == n + 1 + m) return minf; int sumf = 0, f; for (int i = head[u]; i != -1 && minf; i = e[i][1]) { int v = e[i][0]; if (level[v] == level[u] + 1 && e[i][2] > 0) { f = dfs(v, minf < e[i][2] ? minf : e[i][2]); e[i][2] -= f; e[i ^ 1][2] += f; minf -= f; sumf += f; } } return sumf; } inlinevoidaddedge(int f, int to, int w){ e[index][0] = to; e[index][1] = head[f]; head[f] = index; e[index++][2] = w; e[index][0] = f; e[index][1] = head[to]; head[to] = index; e[index++][2] = 0; } inlineintdinic(){ int sum = 0; while (bfs()) sum += dfs(0, INF); return sum; } vector<int> vc; intmain(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> m >> n; for (int i = 0; i <= m + n + 1; i++) head[i] = -1; index = 0; int sum = 0; int x, y, w; for (int i = 1; i <= m; i++) { cin >> w; addedge(0, i, w); while (cin.peek() != '\n') { cin >> y; addedge(i, y + m, INF); } sum += w; } for (int i = m + 1; i <= m + n; i++) { cin >> w; addedge(i, n + m + 1, w); } int ans = sum - dinic(); for (int i = 1; i < n + m + 1; i++) if (vis[i]) vc.push_back(i); sort(vc.begin(), vc.end()); cout << ans << endl; return0; }
