网络流24题之二太空飞行计划问题

内容

填坑

题目描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

1 2
1 2 3
17

模型：

最大权闭合图问题，可以转化成最小割问题，进而用最大流解决。

实现：

把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。

1、从S向每个Xi连接一条容量为该点收入的有向边。
2、从Yi向T连接一条容量为该点支出的有向边。
3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。

统计出所有实验的收入值和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点，也就是最后一次增广找到阻塞流时能从S访问到的顶点。

定义一个割划分出的S集合为一个解，那么割集的容量之和就是(未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。A集合中所有顶点的权值之和记为Total，那么Total – Cut就是(被选的A集合中的顶点的权值 – 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 30010
#define N 30100
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
struct node
{
    int from,to,next,flow;
}e[M];
int tot=-1,st[M],dis[N],q[N][2],vis[N];
int n,m,x,y,z;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
int bfs(int s,int t)
{
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    memset(vis,0,sizeof vis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                vis[e[i].to]=1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=st[x];~i;i=e[i].next)
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            return ans;
        }
    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
main()
{
    scanf("%d%d",&m,&n);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    int T=n+m+1;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        sum+=x;
        add(0,i,x),add(i,0,0);
        char ch=getchar();
        while((ch=getchar())!='\n')
        {
            x=ch-'0';
            while((ch=getchar())&&ch>='0'&&ch<='9')
                x=x*10+ch-'0';
            add(i,x+m,0x3f3f3f3f),add(x+m,i,0);
            if(ch=='\n')break;
        }
    }
    for (int i=1;i<=n;i++)
        scanf("%d",&x),add(i+m,T,x),add(T,i+m,0);
    int ans=sum-Dinic(0,T);
    int E[M],cnt=0;
    memset(E,0,sizeof E);
    for (int i=1;i<=m;i++)   if (vis[i]) E[++cnt]=i;
    for (int i=1;i<cnt;i++)  printf("%d ",E[i]);
    printf("%d\n",E[cnt]);
    cnt=0;memset(E,0,sizeof E);
    for (int i=1;i<=n;i++)   if (vis[i+m]) E[++cnt]=i;
    for (int i=1;i<cnt;i++)  printf("%d ",E[i]);
    printf("%d\n",E[cnt]);
    printf("%d\n",ans);
}

网络流24题之二 太空飞行计划问题

题目描述

输入输出格式

输入输出样例

网络流24题之二太空飞行计划问题