因为选择第k个实验一定要选择它所需要的仪器,所以本题可以转换成最大权闭合图问题

建图方法

把每个实验和每个仪器都看成一个点

S向每个实验连一条容量为赞助商同意支付该实验的费用,每个仪器向T连一条容量为仪器的费用的边

每个实验向所需要的仪器连一条容量为正无穷的边

最大收益就是所有实验的费用加起来减去最小割

//本题可以转换成最大权闭合图问题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<sstream>
#include<string>

using namespace std;

const int N=110;
const int M=6010;
const int INF=1e8;

int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int cur[N],q[N],d[N];
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs(){
    memset(d,-1,sizeof(d));
    int hh=0,tt=0;
    q[tt++]=S;
    d[S]=0;
    cur[S]=h[S];
    while(tt!=hh){
        int t=q[hh++];
        if(hh==N) hh=0;

        for(int i=h[t];i!=-1;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[tt++]=ver;
                if(tt==N) tt=0;
            }
        }
    }
    return false;
}

int find(int u,int limit){
    if(u==T) return limit;

    int flow=0;
    for(int i=cur[u];i!=-1&&flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i]){
            int t=find(ver,min(f[i],limit-flow));
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic(){
    int maxflow=0;
    while(bfs()){
        int flow;
        while(flow=find(S,INF)) maxflow+=flow;
    }
    return maxflow;
}

void dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int ver=e[i];
        if(!st[ver]&&f[i]){
            dfs(ver);
        }
    }
}

int main(){
    int tot=0;
    memset(h,-1,sizeof(h));
    scanf("%d%d",&m,&n);
    S=N-2,T=N-1;
    getchar();
    for(int i=1;i<=m;++i){
        string line;
        getline(cin,line);
        stringstream sin(line);

        int val;
        sin>>val;
        tot+=val;
        add(S,i,val);

        int k;
        while(sin>>k){
            add(i,k+m,INF);
        }
    }

    for(int i=1;i<=n;++i){
        int val;
        scanf("%d",&val);
        add(i+m,T,val);
    }

    int res=dinic();

    dfs(S);

    for(int i=1;i<=m;++i){
        if(st[i]) cout<<i<<" ";
    }
    cout<<"\n";

    for(int i=m+1;i<=n+m;++i){
        if(st[i]) cout<<i-m<<" ";
    }
    cout<<"\n";

    cout<<tot-res<<"\n";

    return 0;
}