【洛谷P2762】太空飞行计划问题

题目链接

太空飞行计划问题

题目描述

W教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合\(E={E_1，E_2，…，E_m}\)，和进行这些实验需要使用的全部仪器的集合\(I={I_1，I_2，…I_n}\)。实验\(E_j\)需要用到的仪器是\(I\)的子集。配置仪器\(I_k\)的费用为\(c_k\)美元。实验\(E_j\)的赞助商已同意为该实验结果支付\(p_j\)美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入格式

第1行有2个正整数\(m\)和\(n\)。\(m\)是实验数，\(n\)是仪器数。接下来的\(m\)行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的\(n\)个数是配置每个仪器的费用。

输出格式

第1行是实验编号；第2行是仪器编号；最后一行是净收益。

样例输入

2 3
10 1 2
25 2 3
5 6 7

样例输出

1 2
1 2 3
17

说明/提示

\(n,m \le 50\)
这道题数据是在windows生成的，输入数据中所有的换行都是‘\r\n‘而不是‘\n‘
读入某实验需要用到的仪器编号的时候，可以这么读入。

char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
{//tool是该实验所需仪器的其中一个      
    //这一行，你可以将读进来的编号进行储存、处理，如连边。
    if (tool==0) 
        ulen++;
    else {
        while (tool) {
            tool/=10;
            ulen++;
        }
    }
    ulen++;
}

题解

每个项目可以获得一定的价值，每个项目都有一些器材的要求，每个器材需要花费一定的金额
那么我们考虑这样一种网络流的建图方法。
我们把每个项目作为一个点，\(s\)向每个项目连一条长度为这个项目能提供的金额的边，
然后我们把每个器材也都作为一个点，然后每个器材向\(t\)连一条长度为这个器材的花费的边。
然后对于每个项目，向这个项目的每个器材的需求各连一条长度为\(inf\)的边。
然后我们跑这个图的最大流，算出来的最大流表示不选择花费的金额，然后把所有项目能提供的金额的和减去这个最大流就是最终答案了。
证明（假）：
我们考虑只有一个项目的情况，如果这个项目的贡献大于他需要的每个器材的费用和，那么最大流就是每个器材的费用和，最后答案是满足这个项目的需求所能得到的金额。
如果这个项目的贡献小于他需要的每个器材的费用和，那么最大流就是这个项目的贡献，最后答案是0。
但是因为即使这个项目的贡献不能支撑每个的费用和，这个用户经过这些器材到达\(t\)的路径还是有流量的，也就是说如果完成这个项目会亏钱，但是完成这个项目之后可以减少完成另一个项目的需求的花费（也就是说两个项目的单独贡献都为负数，但是因为有一些器材需求的重合，使两个项目一起完成的贡献为正），这种情况会使另一个项目通过这些器材到\(t\)的残量减小，从而增加答案。


接下来是重点：
题目要求给出达到这么多净收益的方案，因为无论求出选择的项目或者选择的器材，那么肯定可以求出另外一个的选择（显然的）。
那么我们考虑选择的项目和不选择的项目有什么区别。
首先，一个项目如果被选择了的话，那么\(s\)到这个项目的流量肯定是不满的。
但是如果\(s\)到一个项目的流量是满的，这个项目不一定是不选择的（比如上面所说的这个项目和其他项目一起完成净收益才能为正）。
那么我们会发现这个项目会有这么一个特点：
这个项目必定有一个和其他选择的（流量不满）项目相同的器材，那么如果让那个流量不满的项目到这个器材的流量增加，那么就可以让这个项目的流量减小，变成流量不满的项目。
简单来说就是在残量网络上有\(s\)到这个项目的流量。
那么我们根据最后一次\(bfs\)所得的\(dis[]\)值来判断哪些项目选择了，然后这些项目需要的器材一定是要选择的。
那么我们就可以输出答案了。
上代码：

#include<bits/stdc++.h>
#define inf 2000000000
using namespace std;
int n,m,x;
int ans,sum;
int ss[5009];
int t;
char c;
int s[5009];
int to[5009][5009],lt[5009];
struct aa{
    int to,nxt,w;
}p[5009];
int h[5009],len=1;
void add(int u,int v,int w){
    p[++len].to=v;
    p[len].nxt=h[u];
    p[len].w=w;
    h[u]=len;
    p[++len].to=u;
    p[len].nxt=h[v];
    p[len].w=0;
    h[v]=len;
}
int dis[5009],uu[5009],l,r;
bool bfs(){
    memset(dis,-1,sizeof(dis));
    dis[0]=0;
    uu[l=r=1]=0;
    while(l<=r){
        int u=uu[l++];
        for(int j=h[u];j;j=p[j].nxt){
            if(p[j].w && dis[p[j].to]==-1){
                dis[p[j].to]=dis[u]+1;
                uu[++r]=p[j].to;
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int mx){
    if(u==t) return mx;
    int oo=0,xx;
    for(int j=h[u];j;j=p[j].nxt){
        if(dis[p[j].to]==dis[u]+1){
            xx=dfs(p[j].to,min(mx,p[j].w));
            oo+=xx;
            mx-=xx;
            p[j].w-=xx;
            p[j^1].w+=xx;
        }
    }
    return oo;
}
int main(){
    scanf("%d%d",&m,&n);
    t=n+m+1;
    for(int j=1;j<=m;j++){
        scanf("%d",&x);
        ss[j]=x;
        sum+=x;
        add(0,j,x);
        while(1){
            scanf("%c",&c);
            if(c!=' ') break;
            scanf("%d",&x);
            to[j][++lt[j]]=x;
            add(j,m+x,inf);
        }
    }
    for(int j=1;j<=n;j++){
        scanf("%d",&x);
        add(m+j,t,x);
    }
    while(bfs()) ans+=dfs(0,inf);
    for(int j=1;j<=m;j++)
        if(dis[j]!=-1) printf("%d ",j);
    puts("");
    for(int j=1;j<=n;j++)
        if(dis[j+m]!=-1) printf("%d ",j);
    puts("");
    printf("%d",sum-ans);
    return 0;
}

【洛谷P2762】太空飞行计划问题

原文：https://www.cnblogs.com/linjiale/p/12025259.html