太空飞行计划问题

解题思路

本题给了很多实验，完成每个实验能获得一定的收益，还有很多器材，每个实验需要对应的一些器材，每个器材都有一个花费。

可以发现想完成每个实验都需要购买对应的器材，如果将所有器材的权值设置成负数，所有实验的权值设置成正数，如果将所有实验向对应的器材连一条边，那么可以发现任何一个原问题的可行方案都会对应到图中的一个闭合子图。

因此本题求的最大净收益其实就是图中的最大权闭合子图，因此可以用求最大权闭合子图的方法来求，从源点向所有实验连一条容量是收益的边，从所有器材向汇点连一条容量是花费的边，从所有实验向对应的器材连一条容量是 $+\infty$ 的边。

因此本题是经典的最大权闭合子图问题的应用，最大权闭合子图 $=$ 正权点的权值和 $-$ 最小割。

本题还要输出方案，可以从最小割中推出最大权闭合子图，就是 $S - \lbrace s \rbrace$，即所有从源点能搜到的点（除源点）。

C++ 代码

#include <iostream>
#include <cstring>
#include <sstream>

using namespace std;

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

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
bool st[N]; //记录每个点能否从源点搜索到，能就是 S 集合，不能就是 T 集合

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

void dfs(int u) //从源点往下爆搜找出割的方案，搜到的点属于 S 集合，搜不到的点属于 T 集合
{
    st[u] = true;

    for(int i = h[u]; i != -1; i = ne[i])
        if(w[i])
        {
            int j = e[i];
            if(!st[j]) dfs(j);
        }
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

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

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点能传输的最大流量，流量上限是 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //最小割
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h); //初始化邻接表

    S = 0, T = n + m + 1; //源点、汇点
    int sum = 0; //记录正权点的权值和
    getchar(); //过滤掉第一行最后的回车
    for(int i = 1; i <= n; i++)
    {
        int x, id;
        string line;
        getline(cin, line);
        stringstream ssin(line);

        ssin >> x;
        add(S, i, x); //从源点向每个实验连一条容量是收益的边

        sum += x; //累加正权点的权值

        while(ssin >> id) add(i, n + id, INF); //从每个实验向器材连一条容量是 INF 的边
    }

    for(int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        add(n + i, T, x); //从每个器材向汇点连一条容量是花费的边
    }

    int res = sum - dinic(); //净收益

    dfs(S); //爆搜找出割的方案

    //闭合子图 = S - {s}
    for(int i = 1; i <= n; i++) //枚举实验
        if(st[i])
            printf("%d ", i); //属于 S 集合的实验就是闭合子图中的实验
    puts("");

    for(int i = n + 1; i <= n + m; i++) //枚举器材
        if(st[i])
            printf("%d ", i - n); //属于 S 集合的器材就是闭合子图中的器材
    puts("");

    printf("%d\n", res);

    return 0;
}