[网络流24题] 太空飞行计划问题（最大权闭合子图模型）

题意

该模型为最大权闭合子图模型（看了题解才知道）。
即，给定若干个点，每个点有正权值和负权值，选择一个权值则必须选择其后继点，求权值最大子图。
模型解法即证明学习自 https://blog.csdn.net/can919/article/details/77603353

题解

考虑建图：
源点与所有实验连边，边流量为实验所得收益
所有仪器与汇点连边，边流量为仪器所需消耗
对每个实验与其所需仪器连边，边流量为无穷大

考虑最小割：
对于割源点与实验的边的意义，因为边流量是收益，所以割掉该边代表不进行该实验。
对于割仪器与汇点的边的意义，因为该边流量代表消耗，所以割掉该边代表使用该仪器。

这样一个割的集合为{所有不进行的实验+需要使用的仪器}
我们只需要求出最小的割集，最后使用所有实验利益减掉最小割即可，这样得到的就是{进行的实验收益+不进行的实验收益 - 不进行的实验收益 - 需要使用的仪器费用} = {进行的实验收益 - 需要使用的仪器费用}。

根据最大流最小割定理，直接跑最大流即可。

对于输出路径：
在dinic的残余图中，若某点深度为-1，无法从源点到达，则说明源点到该点的边是割集中的边，该实验为不进行的实验。直接输出这些实验与这些实验所需仪器即可。

code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 200 + 10;
const int maxm = maxn << 4;
const int mod = 1e9 + 7;

struct Edge{
    int to,cap;
    int nxt;
}edges[maxm];

int head[maxn],tot = 0;
int vis[maxn],deep[maxn],cur[maxn];


vector<int> E[maxn];

void addedge(int u,int v,int c)
{
    edges[tot] = {v,c,head[u]};
    head[u] = tot++;
}

bool bfs(int s,int t)
{
    memset(deep,-1,sizeof(deep));
    for(int i = 0;i <= maxn;++i) cur[i] = head[i];
    deep[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int i = head[v];i != -1;i = edges[i].nxt){
            Edge &e = edges[i];
            if(e.cap > 0 && deep[e.to] == -1){
                deep[e.to] = deep[v]+1;
                que.push(e.to);
            }
        }
    }
    if(deep[t] == -1) return false;
    return true;
}

int dfs(int v,int t,int f){
    if(!f || v == t) return f;
    int flow = 0,d;
    for(int &i = cur[v];i != -1;i = edges[i].nxt){
        Edge &e = edges[i];
        if(e.cap > 0 && deep[e.to] == deep[v]+1){
            d = dfs(e.to,t,min(e.cap,f));
            flow += d;
            f -= d;
            edges[i].cap -= d;
            edges[i^1].cap += d;
            if(!f) break;
        }
    }
    if(!flow) deep[v] = -2;
    return flow;
}

int dinic(int s,int t)
{
    int res = 0;
    while(bfs(s,t)){
        res += dfs(s,t,inf);
    }
    return res;
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    memset(head,-1,sizeof(head));
    int s = 0,t = 200;
    int n,m;
    cin>>n>>m;
    int sum = 0;
    getchar();
    for(int i = 1;i <= n;++i){
        string sp;
        getline(cin,sp);    //单行读入到sp中
        stringstream ss(sp);    //字符串创建流
        int p;
        ss>>p;              //从流中读入
        sum += p;
        addedge(s,i,p);
        addedge(i,s,0);
        int x;
        while(ss>>x){
            E[i].push_back(x);
            addedge(i,x + n,inf);
            addedge(x + n, i, 0);
        }
    }
    for(int i = 1;i <= m;++i){
        int tmp;
        cin>>tmp;
        addedge(i+n,t,tmp);
        addedge(t,i+n,0);    
    }
    int mf = dinic(s,t);
    int res = sum - mf;
    vector<int> ans;

    for(int i = 1;i <= n;++i){
        if(deep[i] != -1){
            ans.push_back(i);
        }
    }

    memset(vis,0,sizeof(vis));
    for(int i = 0;i < ans.size();++i){
        if(!i) printf("%d",ans[i]);
        else printf(" %d",ans[i]);
        for(int j = 0;j < E[ans[i]].size();++j){
            vis[E[ans[i]][j]] = 1;
        }
    }
    puts("");
    int cnt = 0;
    for(int i = 1;i <= 50;++i){
        if(vis[i]){
            if(!cnt)printf("%d",i);
            else printf(" %d",i);
            cnt++;
        }
    }
    puts("");
    printf("%d\n",res);


   return 0;
}