太空飞行计划问题

题目描述

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

说明

感谢@zhouyonglong 提供spj

建议先看一下弱化版。

思路：最大权闭合子图+输出方案

网络流输出方案，好神奇。

先用土法子水了40分。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 const int maxm=300000;
 5 const int inf=1e8;
 6 int n,m,s,t,tw,tot;
 7 int a,b,c;
 8 int l[maxn],dw[maxn],map[maxn][maxn];
 9 bool v[maxn],tv[maxn];
10 inline int min_(int x,int y){return x<y?x:y;}
11 int nl,tl,ret;
12 char ch[maxm];
13 int read(int&nl){
14     ret=0;
15     while(nl<tl&&(ch[nl]<'0'||ch[nl]>'9')) nl++;
16     for(;nl<tl&&ch[nl]>='0'&&ch[nl]<='9';nl++) ret=ret*10+ch[nl]-'0';
17     return ret;
18 }
19 int h[maxn],hs=1;
20 struct edge{int s,n,w;}e[maxm];
21 void add(int x,int y,int z){
22     e[++hs]=(edge){y,h[x],z},h[x]=hs;
23     e[++hs]=(edge){x,h[y]},h[y]=hs;
24 }
25 int d[maxn],q[maxn],head,tail;
26 void bfs(){
27     memset(d,0,sizeof(d));
28     head=tail=0;
29     d[s]=1,q[head++]=s;
30     while(head>tail){
31         a=q[tail++];
32         for(int i=h[a];i;i=e[i].n)
33         if(!d[e[i].s]&&e[i].w){
34             d[e[i].s]=d[a]+1;
35             if(e[i].s==t) return;
36             q[head++]=e[i].s;
37         }
38     }
39 }
40 int ap(int k,int w){
41     if(k==t) return w;
42     int uw=w;
43     for(int i=h[k];i&&uw;i=e[i].n)
44     if(d[e[i].s]==d[k]+1&&e[i].w){
45         int nw=ap(e[i].s,min_(uw,e[i].w));
46         if(nw) e[i].w-=nw,e[i^1].w+=nw,uw-=nw;
47         else d[e[i].s]=0;
48     }
49     return w-uw;
50 }
51 void Dinic(){while(bfs(),d[t]) tw+=ap(s,inf);}
52 int main(){
53     freopen("shuttle.in","r",stdin);
54     freopen("shuttle.out","w",stdout);
55     scanf("%d %d
",&n,&m);
56     s=0,t=n+m+1;
57     for(int i=1;i<=n;i++){
58         gets(ch);
59         nl=0,tl=strlen(ch),a=read(nl),map[i][l[i]++]=a,tot+=a;
60         add(s,i,a);
61         while(a=read(nl),a) add(i,a+n,inf),map[i][l[i]++]=a;
62     }
63     for(int i=1;i<=m;i++){
64         scanf("%d",&a);
65         add(n+i,t,a);
66         dw[i]=h[n+i];
67     }
68     Dinic();
69     for(int i=1;i<=m;i++) if(!e[dw[i]].w) v[i]=1;
70     for(int i=1;i<=n;i++)
71     for(int j=1;j<l[i]&&v[map[i][j]];j++)
72     if(j+1==l[i]){
73         printf("%d ",i);
74         for(int k=1;k<l[i];k++) tv[map[i][k]]=1;
75     }
76     putchar('
');
77     for(int i=1;i<=m;i++) if(tv[i]) printf("%d ",i);
78     putchar('
');
79     printf("%d
",tot-tw);
80     return 0;
81 }

40分代码（以资纪念）

然后去看题解，然后最小割不就是把图分为了s集和j集嘛，求一下s集不就好了吗。

因为与s相连的都是方案，如果需要这个方案，那么它的结余一定为正，即从s到它的流仍有流量。

然而我的土法子为什么错了，因为我找到的是机器。

代码实现：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 const int maxm=300000;
 5 const int inf=1e8;
 6 int n,m,s,t,tw,tot;
 7 int a,b,c;
 8 int l[maxn],dw[maxn],map[maxn][maxn];
 9 bool v[maxn<<1];
10 inline int min_(int x,int y){return x<y?x:y;}
11 int nl,tl,ret;
12 char ch[maxm];
13 int read(int&nl){
14     ret=0;
15     while(nl<tl&&(ch[nl]<'0'||ch[nl]>'9')) nl++;
16     for(;nl<tl&&ch[nl]>='0'&&ch[nl]<='9';nl++) ret=ret*10+ch[nl]-'0';
17     return ret;
18 }
19 int h[maxn],hs=1;
20 struct edge{int s,n,w;}e[maxm];
21 void add(int x,int y,int z){
22     e[++hs]=(edge){y,h[x],z},h[x]=hs;
23     e[++hs]=(edge){x,h[y]},h[y]=hs;
24 }
25 int d[maxn],q[maxn],head,tail;
26 void bfs(){
27     memset(d,0,sizeof(d));
28     head=tail=0;
29     d[s]=1,q[head++]=s;
30     while(head>tail){
31         a=q[tail++];
32         for(int i=h[a];i;i=e[i].n)
33         if(!d[e[i].s]&&e[i].w){
34             d[e[i].s]=d[a]+1;
35             if(e[i].s==t) return;
36             q[head++]=e[i].s;
37         }
38     }
39 }
40 int ap(int k,int w){
41     if(k==t) return w;
42     int uw=w;
43     for(int i=h[k];i&&uw;i=e[i].n)
44     if(d[e[i].s]==d[k]+1&&e[i].w){
45         int nw=ap(e[i].s,min_(uw,e[i].w));
46         if(nw) e[i].w-=nw,e[i^1].w+=nw,uw-=nw;
47         else d[e[i].s]=0;
48     }
49     return w-uw;
50 }
51 void Dinic(){while(bfs(),d[t]) tw+=ap(s,inf);}
52 int main(){
53     freopen("shuttle.in","r",stdin);
54     freopen("shuttle.out","w",stdout);
55     scanf("%d %d
",&n,&m);
56     s=0,t=n+m+1;
57     for(int i=1;i<=n;i++){
58         gets(ch);
59         nl=0,tl=strlen(ch),a=read(nl),map[i][l[i]++]=a,tot+=a;
60         add(s,i,a);
61         while(a=read(nl),a) add(i,a+n,inf),map[i][l[i]++]=a;
62     }
63     for(int i=1;i<=m;i++){
64         scanf("%d",&a);
65         add(n+i,t,a);
66         dw[i]=h[n+i];
67     }
68     Dinic();
69     head=tail=0;
70     q[head++]=s,v[s]=1;
71     while(head>tail) for(int i=h[q[tail++]];i;i=e[i].n) if(!v[e[i].s]&&e[i].w) v[e[i].s]=1,q[head++]=e[i].s;
72     for(int i=1;i<=n;i++) if(v[i]) printf("%d ",i);
73     putchar('
');
74     for(int i=1;i<=m;i++) if(v[i+n]) printf("%d ",i);
75     putchar('
');
76     printf("%d
",tot-tw);
77     return 0;
78 }

有一件事，使用左移(<<n大致相当于乘2ⁿ)右移(>>n相当于除2ⁿ)时一定要分清楚哪一个是放大，哪一个是缩小。

这道题COGS也有，而且提供数据，但是建议去洛谷做，因为有SPJ。（其实也没有太大差距）

题目来源：洛谷