太空飞行计划问题

问题叙述

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 3
10 1 2
25 2 3
5 6 7

输出样例#1: 复制

17

极端酷且闭合回路

以各个一个试验跟S连边,流量也低收入

用器材及T连边,流量为消费

将试行和需要器材连inf的限

于是乎可以请最好小割

这时候会见割掉一部分与T相连和及S相连的尽头,但会保证S和T不连通

诸如此类,你选择了一个尝试,就亟须割掉对许器材与T的度

于器材,割掉相当给选

对于实验,割掉相当给无挑

遂显然答案就是试行利益与-最小割=利益以及-最充分流动

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 struct Node
  8 {
  9   int next,to,c;
 10 }edge[200001],edge2[200001];
 11 int num=1,head[1001],cur[1001],n,m,dist[1001],ans,sum,maxflow,Max;
 12 void add(int u,int v,int c)
 13 {
 14   num++;
 15   edge[num].next=head[u];
 16   head[u]=num;
 17   edge[num].to=v;
 18   edge[num].c=c;
 19 }
 20 bool get(int i)
 21 {
 22   char ch=getchar();
 23   while (ch==' ') ch=getchar();
 24   int x=0;
 25   while (ch>='0'&&ch<='9') 
 26     {
 27       x=x*10+ch-'0';
 28       ch=getchar();
 29     }
 30   add(i,m+x,2e9);
 31   add(m+x,i,0);
 32   if (ch=='\n') return 0;
 33   return 1;
 34 }
 35 bool bfs(int S,int T)
 36 {int i;
 37   memset(dist,-1,sizeof(dist));
 38   queue<int>Q;
 39   Q.push(S);
 40   dist[S]=1;
 41   while (!Q.empty())
 42     {
 43       int u=Q.front();
 44       Q.pop();
 45       for (i=head[u];i;i=edge[i].next)
 46     {
 47       int v=edge[i].to;
 48       if (edge[i].c>0&&dist[v]==-1)
 49         {
 50           dist[v]=dist[u]+1;
 51           Q.push(v);
 52         }
 53     }
 54     }
 55   if (dist[T]==-1) return 0;
 56   return 1;
 57 }
 58 int dfs(int x,int flow,int des)
 59 {
 60   int res=0;
 61   if (x==des) return flow;
 62   for (int &i=cur[x];i;i=edge[i].next)
 63   {
 64       int v=edge[i].to;
 65       if (dist[v]==dist[x]+1&&edge[i].c)
 66     {
 67       int tmp=dfs(v,min(flow-res,edge[i].c),des);
 68           if (tmp<0) continue;
 69           edge[i].c-=tmp;
 70           edge[i^1].c+=tmp;
 71           res+=tmp;
 72           if (res==flow) return res;
 73     }
 74   }
 75   return res;
 76 }
 77 void Dinic(int S,int T)
 78 {
 79   maxflow=0;
 80   while (bfs(S,T))
 81     {
 82       memcpy(cur,head,sizeof(cur));
 83       int a=0;
 84       while (a=dfs(S,2e9,T)) maxflow+=a;
 85     }
 86   return;
 87 }
 88 int main()
 89 {int i,val,S,T,j;
 90   cin>>m>>n;
 91   for (i=1;i<=m;i++)
 92     {
 93       scanf("%d",&val);
 94       sum+=val;
 95       add(0,i,val);
 96       add(i,0,0);
 97       while (get(i));
 98     }
 99   for (i=1;i<=n;i++)
100     {
101       scanf("%d",&val);
102       add(m+i,m+n+1,val);
103       add(m+n+1,m+i,0);
104     }
105   S=0;T=m+n+1;
106   memcpy(edge2,edge,sizeof(edge2));
107   Dinic(S,T);
108   ans=maxflow;
109   ans=sum-ans;
110   cout<<ans;
111 }

 

发表评论

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