首页 > 代码库 > 网络流24T 太空飞行计划问题
网络流24T 太空飞行计划问题
题目背景
题目描述
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 310 1 225 2 35 6 7
输出样例#1：
1 21 2 317
最大权闭合子图
挺裸的建模
这题目需要spj啊
所以不要去没spj的题库啊比如说codevs？
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn = 110000;const int INF = 0x7fffffff;int n,m,S,T;struct node{ int next,v,w;}edge[maxn];int dis[maxn];int que[maxn],head[maxn];int num=1;void add_edge(int u,int v,int w){ edge[++num].v=v;edge[num].w=w;edge[num].next=head[u];head[u]=num; edge[++num].v=u;edge[num].w=0; edge[num].next=head[v];head[v]=num;}bool bfs(){ memset(dis,-1,sizeof(dis)); int h=0,t=1; que[h]=dis[0]=0; while(h<t) { int u=que[h++]; if(h==maxn)h=0; for(int i=head[u];i;i=edge[i].next) { int v=edge[i].v; if(edge[i].w&&dis[v]<0) { que[t++]=v; dis[v]=dis[u]+1; if(t==maxn)t=0; } } } if(dis[T]==-1)return false; return true;}int dfs(int x,int f){ if(x==T) return f; int mn=0,w; for(int i=head[x];i;i=edge[i].next) { if(edge[i].w&&dis[edge[i].v]==dis[x]+1) { w=f-mn; w=dfs(edge[i].v,min(w,edge[i].w)); edge[i].w-=w; edge[i^1].w+=w; mn+=w; if(mn==f)return f; } } if(!mn)dis[x]=-1; return mn;}int main(){ int sum=0; scanf("%d%d",&m,&n);S=0,T=n+m+1; for(int a,i=1;i<=m;++i) { bool flag=0; scanf("%d",&a);sum+=a; add_edge(S,i,a); while(11101001) { int x=0; char c=getchar(); while(c<‘0‘||c>‘9‘) c=getchar(); while(c<=‘9‘&&c>=‘0‘){x=x*10+c-‘0‘,c=getchar();} add_edge(i,x+m,INF);if(c==10||c==13)break; } } for(int a,i=1;i<=n;++i) scanf("%d",&a),add_edge(m+i,T,a); int ans=0; while(bfs()) ans+=dfs(S,INF); for(int i=1;i<=m;++i) if(dis[i]!=-1)printf("%d ",i); puts(""); for(int i=m+1;i<=T;i++) if(dis[i]!=-1)printf("%d ",i-m); puts(""); printf("%d\n",sum-ans); return 0;}
网络流24T 太空飞行计划问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。