航天科工纱流24题:P2762 太空飞行计划问题

P2762 太空飞行计划问题

问题背景

问题叙述

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:

2 3
10 1 2
25 2 3
5 6 7

输出样例#1:

1 2
1 2 3
17

说明

感谢@zhouyonglong 提供spj

分析

网流经典建模题,最老权闭合子图,注意建图,

确立源点S,汇点T,每个实验向S连边容量为低收入,每个器材向T连边容量为开销,其他的边容量为刚刚无根本,求最好小割(=最特别流动);

 

code

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 
  6 using namespace std; 
  7 
  8 const int INF = 0x7fffffff;
  9 const int MAXN = 1010;
 10 struct Edge{
 11     int to,c,nxt;
 12 }e[10010];
 13 
 14 int head[MAXN],dis[MAXN];
 15 int s,t,tot=1;
 16 queue<int>q;
 17 
 18 int read(int &x)
 19 {
 20     x = 0;char ch = getchar();
 21     for (; ch<'0'||ch>'9'; ch = getchar());
 22     for (; ch>='0'&&ch<='9'; ch = getchar())
 23         x = x*10+ch-'0';
 24     if (ch==10||ch==13) return 0;
 25     return 1;
 26 }
 27 void add_edge(int u,int v,int w)
 28 {
 29     e[++tot].c = w,e[tot].to = v,e[tot].nxt = head[u];
 30     head[u] = tot;
 31     e[++tot].c = 0,e[tot].to = u,e[tot].nxt = head[v];
 32     head[v] = tot;
 33 }
 34 bool bfs()
 35 {
 36     memset(dis,-1,sizeof(dis));
 37     dis[s] = 0;
 38     q.push(s);
 39     while (!q.empty())
 40     {
 41         int u = q.front();
 42         q.pop();
 43         for (int i=head[u]; i; i=e[i].nxt)
 44         {
 45             int v = e[i].to;
 46             if (dis[v]==-1&&e[i].c>0)
 47             {
 48                 dis[v] = dis[u]+1;
 49                 q.push(v);
 50             }
 51         }
 52     }
 53     return dis[t]!=-1;
 54 }
 55 int dfs(int u,int low)
 56 {
 57     if (u==t) return low;
 58     int w,tmp = low;
 59     for (int i=head[u]; i; i=e[i].nxt)
 60     {
 61         int v = e[i].to;
 62         if (dis[v]==dis[u]+1&&e[i].c>0)
 63         {
 64             w = dfs(v,min(e[i].c,low));
 65             e[i].c -= w;
 66             e[i^1].c += w;
 67             low -= w;
 68         }
 69     }
 70     return tmp - low;
 71 }
 72 int main()
 73 {
 74     int ans = 0,sum = 0,m,n,flag;
 75     read(m),read(n);
 76     s = 0,t = n+m+1;
 77     for (int x,i=1; i<=m; ++i)
 78     {
 79         flag = 1;
 80         read(x);
 81         sum += x;
 82         add_edge(s,i,x);
 83         while (flag) 
 84         {
 85             flag = read(x);
 86             add_edge(i,x+m,INF);
 87         }
 88     }
 89     for (int x,i=1; i<=n; ++i)
 90     {
 91         read(x);
 92         add_edge(i+m,t,x);
 93     }
 94     while (bfs())
 95         ans += dfs(s,INF);
 96     for (int i=1; i<=m; ++i)
 97         if (dis[i]!=-1) printf("%d ",i);
 98     printf("\n");
 99     for (int i=m+1; i<=t; ++i)
100         if (dis[i]!=-1) printf("%d ",i-m);
101     printf("\n%d\n",sum-ans);
102     return 0;
103 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注