P2762 太空飞行计划问题[最小割]

题目描述

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

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
2 3
10 1 2
25 2 3
5 6 7

输出样例#1:

1
2
3
1 2
1 2 3
17

题解

套路建模,建一个S和T

1.S连向每一个实验,容量为 赞助商同意支付的费用数。
2.每一个实验连向每个仪器,容量为INF。
3.每个仪器连向T,容量为仪器的费用。

最后的答案则为 支付商同意支付的费用的和-最小割。

输出的方案(所进行的实验和配置的仪器)为最后一次建层次图时,h[i]!=-1的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
bool flag;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
if (s=='\n'||s=='\r') flag=true;
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxm=500000;
const int maxn=105;
int m,n,S,T,X,Y,Z,id;
int to[maxm],po[maxn],ne[maxm],w[maxm],p[maxn],sum;
int h[maxn];
queue<int> q;
int a[maxn*4],f[maxn];
vector<int> G[60];
void add(int x,int y,int z)
{
id++;to[id]=y;w[id]=z;ne[id]=po[x];po[x]=id;
}
bool bfs()
{
memcpy(p,po,sizeof(po));
while (!q.empty()) q.pop();
memset(h,-1,sizeof(h));
q.push(S);h[S]=1;
int u=0,v=0;
while (!q.empty())
{
u=q.front();q.pop();
for (int i=po[u];i;i=ne[i])
{
v=to[i];
if (h[v]==-1&&w[i]>0)
{
h[v]=h[u]+1;
q.push(v);
}
}
}
return h[T]!=-1;
}
int dfs(int u,int low)
{
if (u==T||low==0) return low;
int used=0,v;
for (int i=p[u];i;i=ne[i])
{
if (h[to[i]]==h[u]+1)
{
int W=dfs(to[i],min(low-used,w[i]));
used+=W;
p[u]=i;
w[i]-=W;w[i^1]+=W;
if (used==low) return low;
}
}
if (used==0) h[u]=-1;
return used;
}
int ans;
int main()
{
id=1;
m=read();n=read();S=m+n+1,T=m+n+2;
for (int i=1;i<=m;i++)
{
Z=read();ans+=Z;
flag=false;
while (!flag)
{
X=read();G[i].push_back(X);
add(i+n,X,233333333);add(X,i+n,0);
}
a[i+n]=id+1;
add(S,i+n,Z);add(i+n,S,0);
}
for (int i=1;i<=n;i++)
{
a[i]=id+1;
X=read();add(i,T,X);add(T,i,0);
}
while (bfs()) ans-=dfs(S,23333333);
for (int i=n+1;i<=n+m;i++)
{
if (h[i]!=-1)
{
printf("%d ",i-n);
for (int j=G[i-n].size()-1;j>=0;j--)
{
f[G[i-n][j]]=1;
}
}
}
printf("\n");
for (int i=1;i<=n;i++) if (h[i]!=-1) printf("%d ",i);
printf("\n%d\n",ans);
return 0;
}