【網(wǎng)絡(luò)流24題-2】太空飛行計劃網(wǎng)絡(luò)流

2019-11-08 01:54:05

字體：大中小

供稿：網(wǎng)友

題目描述

W 教授正在為國家航天中心計劃一系列的太空飛行。每次太空飛行可進行一系列商業(yè)性實驗而獲取利潤。現(xiàn)已確定了一個可供選擇的實驗集合 E={E1，E2，…，Em}，和進行這些實驗需要使用的全部儀器的集合I={I1， I2，…In}。實驗 Ej需要用到的儀器是I的子集。配置儀器Ik的費用為ck美元。實驗Ej的贊助商已同意為該實驗結(jié)果支付pj美元。W教授的任務(wù)是找出一個有效算法，確定在一次太空飛行中要進行哪些實驗并因此而配置哪些儀器才能使太空飛行的凈收益最大。這里凈收益是指進行實驗所獲得的全部收入與配置儀器的全部費用的差額。【編程任務(wù)】：對于給定的實驗和儀器配置情況，編程找出凈收益最大的試驗計劃。

題目大意

給出可供選擇的實驗和器材的信息，包括實驗經(jīng)費（收入），各個器材的費用（支出），求選用某些實驗取得的最大利潤。

數(shù)據(jù)范圍

（0 < m,n <= 100） m為實驗數(shù),n為儀器數(shù)

樣例輸入

2 3 10 1 2 025 2 3 05 6 7

樣例輸出

1 2 1 2 3 17

解題思路

最大利潤=總收入-最大流將實驗與儀器看做二分圖兩部分的頂點，之間邊權(quán)為無窮大S與實驗連邊，權(quán)值為收入，儀器與T連邊，權(quán)值為支出，答案就是總收入減去最大流

代碼

#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <cmath>#define Maxn 205#define Maxe 23333using namespace std;inline int Getint(){int x=0,f=1;char ch=getchar();while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}int S,T,N,dis[Maxn],GAP[Maxn],h[Maxn],cnt,m,n;struct node{int to,next,v,pair;}e[Maxe];void AddEdge(int x,int y,int v,int pair){e[cnt]=(node){y,h[x],v,pair};h[x]=cnt;}void AddEdge(int x,int y,int v){AddEdge(x,y,v,++cnt+1);AddEdge(y,x,0,++cnt-1);}int SAP(int x,int Maxflow){ if(x==T)return Maxflow; int tmp=Maxflow; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; int flow=min(tmp,e[p].v); if(flow&&dis[x]==dis[y]+1){ int ret=SAP(y,flow); tmp-=ret; e[p].v-=ret; e[e[p].pair].v+=ret; if(!tmp||dis[S]==N)return Maxflow-tmp; } } if(--GAP[dis[x]]==0)dis[S]=N; else GAP[++dis[x]]++; return Maxflow-tmp;}bool vis[Maxn];void Dfs(int x){ vis[x]=1; for(int p=h[x];p;p=e[p].next){ int y=e[p].to; if(!vis[y]&&e[p].v)Dfs(y); }}int SAP(){ memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(GAP,0,sizeof(GAP)); GAP[0]=N; int Ans=0; while(dis[S]<N)Ans+=SAP(S,1<<30); Dfs(S); for(int i=1;i<=m;i++)if(vis[i])cout<<i<<" "; cout<<"/n"; for(int i=1;i<=n;i++)if(vis[i+m])cout<<i<<" "; cout<<"/n"; return Ans;}int main(){ m=Getint(),n=Getint(); int Sum=0,k; S=0,T=m+n+1,N=T+1; for(int i=1;i<=m;i++){ Sum+=k=Getint(); AddEdge(S,i,k); while(int t=Getint())AddEdge(i,t+m,1<<30); } for(int i=1;i<=n;i++)AddEdge(m+i,T,Getint()); cout<<Sum-SAP(); return 0;}

上一篇：抽象類和接口

下一篇：編程中無窮大常量的設(shè)定技巧(ox3f3f3f3f)