网络流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 <= 100)。m是实验数，n是仪器数。接下来的m行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

【结果输出】#

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

【输入文件示例】shuttle.in#

2 3
10 1 2
25 2 3
5 6 7

【输出文件示例】shuttle.out#

1 2
1 2 3
17

题解#

最大权闭合子图很裸的题，复习一下板子

1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-06-13 21:23:24
4
 * @Last Modified by: WildRage
5
 * @Last Modified time: 2017-06-13 21:48:22
6
 */
7
#include<iostream>
8
#include<cstdio>
9
#include<cstring>
10
#include<queue>
11
using namespace std;
12
const int INF=0x7fffffff;
13
struct edge{
14
    int END,next,cap;
15
}v[100005];
16
int first[1005],p;
17
void add(int a,int b,int c){
18
    v[p].END=b;v[p].next=first[a];v[p].cap=c;first[a]=p++;
19
    v[p].END=a;v[p].next=first[b];v[p].cap=0;first[b]=p++;
20
}
21
int cur[1005],dis[1005];
22
bool vis[1005];
23
bool BFS(int S,int E){
24
    memset(vis,0,sizeof(vis));
25
    memset(dis,-1,sizeof(dis));
26
    queue<int> Q;
27
    Q.push(S);
28
    dis[S]=0;vis[S]=1;
29
    while(!Q.empty()){
30
        int u=Q.front();Q.pop();
31
        for(int i=first[u];i!=-1;i=v[i].next){
32
            if(!vis[v[i].END]&&v[i].cap>0){
33
                vis[v[i].END]=1;
34
                dis[v[i].END]=dis[u]+1;
35
                if(v[i].END==E)return 1;
36
                Q.push(v[i].END);
37
            }
38
        }
39
    }
40
    return 0;
41
}
42
int DFS(int S,int E,int a){
43
    if(S==E||a==0)return a;
44
    int flow=0,f;
45
    for(int i=first[S];i!=-1;i=v[i].next){
46
        if(dis[S]+1==dis[v[i].END]&&(f=DFS(v[i].END,E,min(a,v[i].cap)))>0){
47
            v[i].cap-=f;
48
            v[i^1].cap+=f;
49
            flow+=f;
50
            a-=f;
51
        }
52
    }
53
    if(!flow)dis[S]=-1;
54
    return flow;
55
}
56
int Dinic(int S,int E){
57
    int ans=0;
58
    while(BFS(S,E)){
59
        ans+=DFS(S,E,INF);
60
    }
61
    //printf("%d\n",ans);
62
    //while(1);
63
    return ans;
64
}
65
int Main()
66
{
67
    memset(first,-1,sizeof(first));
68
    int n,m;
69
    freopen("shuttle.in","r",stdin);
70
  freopen("shuttle.out","w",stdout);
71
    scanf("%d%d",&n,&m);
72
    int ans=0;
73
    char ch;
74
    for(int x,i=1;i<=n;i++){
75
        scanf("%d",&x);ans+=x;
76
        add(0,i,x);
77
        while(1){
78
            while((ch=getchar())==' ');
79
            ungetc(ch,stdin);
80
            if(ch=='\n'||ch=='\r')break;
81
            scanf("%d",&x);
82
            add(i,x+n,INF);
83
        }
84
    }
85
    for(int x,i=1;i<=m;i++){
86
        scanf("%d",&x);
87
        add(i+n,m+n+1,x);
88
    }
89
    ans=ans-Dinic(0,n+m+1);
90
    for(int i=1;i<=n;i++)
91
        if(dis[i]>=0)
92
            printf("%d ",i);
93
    puts("");
94
    for(int i=1;i<=m;i++)
95
        if(dis[i+n]>=0)
96
            printf("%d ",i);
97
    puts("");
98
    printf("%d\n",ans);
99
    return 0;
100
}
101
int Wild=Main();
102
int main(){;}