做这道题之前建议先看这篇论文，虽然论文里很多地方用了很多术语，但hbt神犇讲得很明白
这篇题解更加偏向于感性理解
把问题放到二分图上，左侧一列点是实验，权值为$p[i]$，右侧一列点是仪器，权值为$c[i]$，左侧向右侧连接了许多条出边
如果想获得$p[i]$，需要保证i的所有出边都被选上了
按照论文里最大权闭合图的做法，实验和源点$s$相连，流量为$p[i]$，仪器和汇点$t$相连，流量为$c[i]$，实验和仪器之间的边流量为$inf$
最终的答案就是实验带来的报酬总和-这个图的最大流，即报酬总和去掉 报酬填补费用的总和 ，就是净收益
我们如何比较感性地理解它呢
求最大流的过程，可以看成用实验的钱消去仪器的钱的过程
而有一些实验可能先被遍历到，而这次实验的报酬小于所需仪器的总花费，即这次实验有点亏，但买了给其他实验用的仪器，而其他实验可以把这些钱补回来
在图上的体现就是，有其他实验的流量沿着反向边流向了这次实验
通过求最小割，我们把图分割成了两块，一块包含源点，一块包含汇点
源点指向的每个联通块中，都至少存在一个点，源点向它的流量$>0$，那么这个联通块里的实验仪器组合才是获利的
那么最终答案就是总获利-最大流，方案就是再进行一次$bfs$，$dep$有值的点，即和源点在同一联通块里的点。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N1 350
#define M1 3010
#define ll long long
#define dd double
#define inf 0x3f3f3f3f
using namespace std; int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
} int n,m,nm,S,T;
int p[N1],c[N1];
struct Edge{
int head[N1],to[M1<<],nxt[M1<<],flow[M1<<],cte;
void ae(int u,int v,int F)
{
cte++; to[cte]=v; flow[cte]=F;
nxt[cte]=head[u]; head[u]=cte;
}
}e; int que[M1],hd,tl,dep[N1],cur[N1];
int bfs(Edge &E)
{
int x,j,v;
memset(dep,-,sizeof(dep)); memcpy(cur,E.head,sizeof(cur));
hd=,tl=; que[++tl]=S; dep[S]=;
while(hd<=tl)
{
x=que[hd++];
for(j=E.head[x];j;j=E.nxt[j])
{
v=E.to[j]; if(dep[v]!=-||!E.flow[j]) continue;
dep[v]=dep[x]+; que[++tl]=v;
}
}
return dep[T]!=-;
}
int dfs(Edge &E,int x,int limit)
{
int j,v,flow,ans=; if(x==T||!limit) return limit;
for(j=cur[x];j;j=E.nxt[j])
{
cur[x]=j; v=E.to[j];
if( dep[v]==dep[x]+ && (flow=dfs(E,v,min(E.flow[j],limit))) )
{
limit-=flow; ans+=flow;
E.flow[j]-=flow; E.flow[j^]+=flow;
if(!limit) break;
}
}
return ans;
}
int use[N1],de;
void Dinic()
{
int mxflow=,x,j,v,i,flag,sum=;
for(i=;i<=m;i++) sum+=p[i];
while(bfs(e)) mxflow+=dfs(e,S,inf);
bfs(e);
for(i=;i<=m;i++) if(dep[i]!=-) printf("%d ",i); puts("");
for(i=m+;i<=m+n;i++) if(dep[i]!=-) printf("%d ",i-m); puts("");
printf("%d\n",sum-mxflow);
} char str[];
int main()
{
scanf("%d%d",&m,&n);
int i,j,x,y,flag,slen; S=m+n+,T=m+n+; e.cte=;
for(i=,slen=;i<=m;i++)
{
p[i]=gint(); e.ae(S,i,p[i]), e.ae(i,S,);
memset(str,,sizeof(str)); cin.getline(str,); slen=;
while(sscanf(str+slen,"%d",&x)==)
{
e.ae(i,x+m,inf); e.ae(x+m,i,);
if(!x) slen++;
else{ while(x) x/=,slen++;}
slen++;
}
}
for(i=m+;i<=m+n;i++) c[i]=gint(), e.ae(i,T,c[i]), e.ae(T,i,);
Dinic();
return ;
}