1. 题目

传送门=￣ω￣=

2. 题解

坑了我好久啊。

这题读入太恶心了。

建图方法

1. 从源点连一条流量为 $p_i$的边到第 $i$个实验上（$p_i$表示第 $i$个实验的收益）
2. 从每个器材连一条流量为 $c_i$的边到汇点上（$c_i$表示第 $i$个器材的价格）
3. 从每个实验连边到它们各自需要的器材上，流量为 $inf$

然后跑最大流。跑完以后剩下的图中，你从源点出发能到达的实验就是能有收益的实验（满流的边不能通过）。这样就能得到答案了。

代码

#include <bits/stdc++.h>
using namespace std;
struct edge{int u,v,c;}e[1000];
int m,n,p[55],c[55],T,from[105],cnt,ans;
bool book[105];
vector<int> g[105];
queue<int> que;
template<typename _Tp>inline bool IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(c=='\n'||c=='\r')return 0;
    return 1;
}
void adde(int a,int b,int c)
{
    g[a].push_back(cnt),e[cnt++]=(edge){a,b,c};
    g[b].push_back(cnt),e[cnt++]=(edge){b,a,0};
}
bool bfs()
{
    while(!que.empty())que.pop();
    memset(book,0,sizeof(book)),que.push(0),book[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(int i=0;i<g[F].size();i++)if(!book[e[g[F][i]].v]&&e[g[F][i]].c)
            from[e[g[F][i]].v]=g[F][i],book[e[g[F][i]].v]=1,que.push(e[g[F][i]].v);
        if(book[T])return 1;
    }
    return 0;
}
void mcf()
{
    int MX=INT_MAX;
    for(int i=from[T];i!=-1;i=from[e[i].u])MX=min(MX,e[i].c);
    for(int i=from[T];i!=-1;i=from[e[i].u])e[i].c-=MX,e[i^1].c+=MX;
    ans-=MX;
}
int main()
{
    IN(m),IN(n),T=n+m+1,from[0]=-1;
    for(int i=1,j,opt;i<=m;i++)
    {
        IN(p[i]),ans+=p[i];
        while(opt=IN(j),1){adde(i,j+m,(int)1e8);if(!opt)break;}
    }
    for(int i=1;i<=n;i++)IN(c[i]);
    for(int i=1;i<=m;i++)adde(0,i,p[i]);
    for(int i=1;i<=n;i++)adde(i+m,T,c[i]);
    while(bfs())mcf();
    for(int i=1;i<=m;i++)if(book[i])printf("%d ",i);
    putchar('\n');
    for(int i=1;i<=n;i++)if(book[i+m])printf("%d ",i);
    printf("\n%d\n",ans);
    return 0;
}