**ISAP最大流**
## 思路
这道题需要收益最大，也就是求出最小割，应使用最大流求解。
## 读入
对于一整行不知道有多少个数据，并且结尾还是`\r\n`，我们可以使用C++的`stringstream`，把整行用`getline`读进一个`string`，然后放入`stringstream`，从里面读取数据
## 建图
* 我们设$0$为超级源点，$n + m + 1$为超级汇点，每个实验对应$[1, m]$，每个仪器对应$[m + 1, n]$
* 对于$\forall i \in [1, m]$
* 从$0$向$i$连边，容量为费用
* 对于$\forall j \in R_i$，从$i$向$m + j$连边，容量为$\infty$
* 对于$\forall j \in [1, n]$
* 从$j + m$向$n + m + 1$连边，容量为费用
## 输出
显然，最终输出的那个数是总费用减最大流。
那么如何输出方案？
根据ISAP的分层原理，我们把`gap`优化去掉~~（貌似这就成普通的SAP了）~~，使得最终流完的深度区分更明显。这样，跑完一遍最大流后，被割掉的点深度趋近于$0$，没被割掉的点深度趋近于$n + m$，那么我们取中间值作为分界线，深度大于这个值的点就是我们留下来的点，输出即可
## 程序实现
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 55;
const int INF = 0x3f3f3f3f;
int n, m;
struct Edge{
int to, val;
Edge *next, *ops;
Edge(int to, int val, Edge *next): to(to), val(val), next(next){}
};
Edge *head[MAXN << 1];
inline void AddEdge(int u, int v, int w) {
head[u] = new Edge(v, w, head[u]);
head[v] = new Edge(u, 0, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
int s, t, dep[MAXN << 1], /*gap[MAXN << 1], */res;
void Bfs() {
memset(dep, -1, sizeof(dep));
//memset(gap, 0, sizeof(gap));
dep[t] = 0; //gap[dep[t]]++;
queue<int> q; q.push(t);
while (!q.empty()) {
int u = q.front(); q.pop();
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (dep[v] != -1) continue;
dep[v] = dep[u] + 1;
//gap[dep[v]]++;
q.push(v);
}
}
}
int Dfs(int u, int flow) {
if (u == t) {
res += flow;
return flow;
}
int used = 0;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val && dep[v] == dep[u] - 1) {
int mi = Dfs(v, std :: min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
used += mi;
}
if (used == flow) return used;
}
}
//gap[dep[u]]--;
//if (gap[dep[u]] == 0) dep[s] = n + m + 3;
dep[u]++;
//gap[dep[u]]++;
return used;
}
void Work() {
res = 0;
Bfs();
while (dep[s] <= n + m + 2) Dfs(s, INF);
}
int main() {
cin >> m >> n;
s = 0; t = n + m + 1;
int tot = 0;
string str;
stringstream ss;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
tot += x;
AddEdge(s, i, x);
ss.clear();
getline(cin, str);
ss << str;
while (ss >> x) AddEdge(i, x + m, INF);
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
AddEdge(i + m, t, x);
}
Work();
/*for (int i = 1; i <= m; i++) cout << dep[i] << ' ';
cout << endl;
for (int i = m + 1; i <= n + m; i++) cout << dep[i] << ' ';
cout << endl;*/
for (int i = 1; i <= m; i++) {
if (dep[i] > n + m >> 1) cout << i << ' ';
}
cout << endl;
for (int i = m + 1; i <= n + m; i++) {
if (dep[i] > n + m >> 1) cout << i - m << ' ';
}
cout << endl;
cout << tot - res << endl;
return 0;
}
```
*PS：虽然本代码可以AC此题，但是由于最后输出方案的方法有一点点玄学成分，所以如果针对这份代码刻意制造毒瘤数据，有可能是可以HACK掉的*