FLOW2 太空飞行计划问题

模型：

最大权闭合图->网络最小割

题意：

现已确定了一个可供选择的实验集合 $E = \{ E_1, E_2, \cdots, E_m \}$，和进行这些实验需要使用的全部仪器的集合 $I = \{ I_1, I_2, \cdots, I_n \}$。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j \subseteq I$。 配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。对于给定的实验和仪器配置情况，找出净收益最大的试验计划。

题解：

最大权闭合子图例题

可以从 $S$ 向每个实验连一条容量为 $p_i$ 的边，每个实验向所需要的仪器连一条容量为 $inf$ 的边，每个仪器向 $T$ 连一条容量为 $c_i$ 的边

假设所有实验都做，再计算出网络图的最小割，最小割就是要花费的钱

答案就是总的能赚的钱减去花费的钱

为什么要看做最小割呢？因为如果某个实验的收益为负数，但是它用到的仪器能为别的实验所用，那么就相当于你花了这个实验的赞助商给你的钱为别的实验买仪器，具象化在网络图上，就是仪器那个点给这个实验一个流，把这个实验流出去的抵消掉了。当然，也会存在那种无论怎么买仪器都不划算的实验，这样的实验有一个特点，因为它不能供给仪器的需求，所以源点到它的残流一定是0，就是说不管是正向边还是反向边都是0，同样的那些可以供给的，源点到它的残留一定大于0，也就是正向边或者反向边大于0，说明做这个实验能赚钱。

然后来看所选择实验和仪器的输出

考虑用dinic跑网络流，注意到最后一遍跑完分层图后的有“存在”点都是最“邻近”超级源点和超级汇点的，也就是采取最小割后，这些点都是与两个超级点在同一集合中的

所以在网络流后枚举一遍每个点在分层图中的深度，有深度（存在）就表示要选择，输出即可

代码：

#include <bits/stdc++.h>
#define fill(x,y) memset(x,y,sizeof x)
#define copy(x,y) memcpy(x,y,sizeof x)
using namespace std;
inline int read(int &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
inline void write(int x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}
const int oo=0x7fffffff;
const int N=100+5,M=N*N+5;
int en=1,h[N],d[N],n,m,s,t,use,cur[N],ans;
struct edge{int n,v,w;}e[M<<1];
inline void add(int x,int y,int z){e[++en]=(edge){h[x],y,z};h[x]=en;}
inline void exadd(int x,int y,int z){add(x,y,z);add(y,x,0);}
bool bfs(int s,int aim){
    fill(d,0);
    copy(cur,h);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].w){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}
int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].w){
            int tp=dfs(y,min(rest,e[i].w),aim);
            rest-=tp;
            e[i].w-=tp;
            e[i^1].w+=tp;
        }
    }
    return flow-rest;
}
int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}
signed main(){
    read(n);read(m);
    s=0;t=n+m+1;
    for(int i=1,x;i<=n;i++){
        read(x);
        ans+=x;
        exadd(s,i,x);
        for(;;){
            char c;
            scanf("%d%c",&x,&c);
            exadd(i,n+x,oo);
            if(c=='\n'||c=='\r') break;
        }
    }
    for(int i=1,x;i<=m;i++){
        read(x);
        exadd(n+i,t,x);
    }
    ans-=dinic(s,t);
    for(int i=1;i<=n;i++) if(d[i])
        write(i),putchar(' ');
    puts("");
    for(int i=1;i<=m;i++) if(d[i+n])
        write(i),putchar(' ');
    puts("");
    write(ans);
}
赏

fighter