题目描述

有 $n$ 个实验，每个实验可以获得一定的赞助费
有 $m$ 个仪器，每个实验需要使用若干仪器，仪器会有一定的消费

求最大利润以及方案
$n, m \leq 50$

输入样例

2 3
10 1 2
25 2 3
5 6 7

输出样例

1 2
1 2 3
17

最大权闭合子图

结论：最大利润 = 正权点之和 - 最小割

不会证明因此省略证明qwq
详细证明请参考 算法进阶课1.3.2最小割之最大权闭合图

输出方案

当选择一个正权点的收益 > 他所连接的负权点的消费时，源点连接这个正权点的边就不会满流

因此从源点出发跑一个 $dfs$ ，只走没有满流（残留网络还有流量）的边
抵达的正权点都是要被选择的

同时所有被选择的正权点所连接的所有负权点也是要被选择的

时间复杂度 $O(网络流的时间复杂度就跟放屁一样)$

C++ 代码

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

using namespace std;

const int N = 110, M = 100010, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
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 ++;
}

int n, m, S, T;
int hs[N], d[N], q[N];

bool bfs()
{
    memset(d, -1, sizeof d);
    d[S] = 0;

    int hh = 0, tt = -1;
    q[ ++ tt] = S;
    hs[S] = h[S];

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1 and f[i])
            {
                d[j] = d[u] + 1;
                hs[j] = h[j];
                if(j == T)  return true;
                q[ ++ tt] = j;
            }
        }
    }
    return false;
}

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

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

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

vector<int> v[N];
bool st[N], st2[N];
void dfs(int u)
{
    st[u] = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!st[j] and f[i])  dfs(j);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;
    S = 0, T = n + m + 1;
    getchar();

    int sum = 0;
    for(int i = 1; i <= n; i ++)
    {
        string s;
        getline(cin, s);
        stringstream ss(s);
        int c;
        ss >> c;
        sum += c;
        add(S, i, c);
        while(ss >> c)
        {
            v[i].push_back(c);
            add(i, n + c, INF);
        }
    }
    for(int i = n + 1; i <= n + m; i ++)
    {
        int c;
        cin >> c;
        add(i, T, c);
    }
    int res = sum - dinic();
    dfs(S);
    for(int i = 1; i <= n; i ++)
        if(st[i])
        {
            printf("%d ", i);
            for(int j : v[i])  st2[j] = true;
        }
    puts("");
    for(int i = 1; i <= m; i ++)
        if(st2[i])  printf("%d ", i);
    printf("\n%d\n", res);
    return 0;
}