线性规划与网络流24题-太空飞行计划问题
【问题分析】
最大权闭合图问题，可以转化成最小割问题，进而用最大流解决。
【建模方法】
把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。 1、从S向每个Xi连接一条容量为该点收入的有向边。 2、从Yi向T连接一条容量为该点支出的有向边。 3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。
统计出所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow。对应的解就是最小割划分出的S集合中的点，也就是最后一次增广找到阻塞流时能从S访问到的顶点。
【建模分析】
定义一个割划分出的S集合为一个解，那么割集的容量之和就是(未被选的A集合中的顶点的权值 + 被选的B集合中的顶点的权值)，记为Cut。A集合中所有顶点的权值之和记为Total，那么Total - Cut就是(被选的A集合中的顶点的权值 - 被选的B集合中的顶点的权值)，即为我们的目标函数，记为A。要想最大化目标函数A，就要尽可能使Cut小，Total是固定值，所以目标函数A取得最大值的时候，Cut最小，即为最小割。
该问题的一般模型为最大权闭合图，相关讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Problem: 线性规划与网络流24题 #2 太空飞行计划问题 | |
| * Author: Guo Jiabao | |
| * Time: 2009.6.26 18:09 | |
| * State: Solved | |
| * Memo: 网络最大流 最小割 | |
| */ | |
| #include <iostream> | |
| #include <cstdio> | |
| #include <cstdlib> | |
| #include <cmath> | |
| #include <cstring> | |
| using namespace std; | |
| const int MAXN=101,MAXM=MAXN*MAXN*2,INF=~0U>>1; | |
| struct edge | |
| { | |
| edge *next,*op; | |
| int t,c; | |
| }*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN]; | |
| int N,M,S,T,EC,Ans,Maxflow; | |
| int Lv[MAXN],Stap[MAXN]; | |
| inline void addedge(int a,int b,int c) | |
| { | |
| ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; | |
| ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; | |
| V[a]->op = V[b]; V[b]->op = V[a]; | |
| } | |
| void init() | |
| { | |
| int i,a,c; | |
| freopen("shut.in","r",stdin); | |
| freopen("shut.out","w",stdout); | |
| scanf("%d%d",&M,&N); | |
| S=0; T=N+M+1; | |
| for (i=1;i<=M;i++) | |
| { | |
| scanf("%d",&c); | |
| addedge(S,i,c); | |
| Ans += c; | |
| for (;;) | |
| { | |
| do c=getchar(); while (c==' '); ungetc(c,stdin); | |
| if (c==10 || c==13) break; | |
| scanf("%d",&a); | |
| addedge(i,a+M,INF); | |
| } | |
| } | |
| for (i=1;i<=N;i++) | |
| { | |
| scanf("%d",&c); | |
| addedge(i+M,T,c); | |
| } | |
| } | |
| bool Dinic_Label() | |
| { | |
| int head,tail,i,j; | |
| Stap[head=tail=0]=S; | |
| memset(Lv,-1,sizeof(Lv)); | |
| Lv[S]=0; | |
| while (head<=tail) | |
| { | |
| i=Stap[head++]; | |
| for (edge *e=V[i];e;e=e->next) | |
| { | |
| j=e->t; | |
| if (e->c && Lv[j]==-1) | |
| { | |
| Lv[j] = Lv[i]+1; | |
| if (j==T) | |
| return true; | |
| Stap[++tail] = j; | |
| } | |
| } | |
| } | |
| return false; | |
| } | |
| void Dinic_Augment() | |
| { | |
| int i,j,delta,Stop; | |
| for (i=S;i<=T;i++) | |
| P[i] = V[i]; | |
| Stap[Stop=1]=S; | |
| while (Stop) | |
| { | |
| i=Stap[Stop]; | |
| if (i!=T) | |
| { | |
| for (;P[i];P[i]=P[i]->next) | |
| if (P[i]->c && Lv[i] + 1 == Lv[j=P[i]->t]) | |
| break; | |
| if (P[i]) | |
| { | |
| Stap[++Stop] = j; | |
| Stae[Stop] = P[i]; | |
| } | |
| else | |
| Stop--,Lv[i]=-1; | |
| } | |
| else | |
| { | |
| delta = INF; | |
| for (i=Stop;i>=2;i--) | |
| if (Stae[i]->c < delta) | |
| delta = Stae[i]->c; | |
| Maxflow += delta; | |
| for (i=Stop;i>=2;i--) | |
| { | |
| Stae[i]->c -= delta; | |
| Stae[i]->op->c += delta; | |
| if (Stae[i]->c==0) | |
| Stop = i-1; | |
| } | |
| } | |
| } | |
| } | |
| void Dinic() | |
| { | |
| while (Dinic_Label()) | |
| Dinic_Augment(); | |
| } | |
| void print() | |
| { | |
| for (int i=1;i<=M;i++) | |
| if (Lv[i]!=-1) | |
| printf("%d ",i); | |
| putchar('\n'); | |
| for (int i=M+1;i<=M+N;i++) | |
| if (Lv[i]!=-1) | |
| printf("%d ",i-M); | |
| Ans -= Maxflow; | |
| printf("\n%d\n",Ans); | |
| } | |
| int main() | |
| { | |
| init(); | |
| Dinic(); | |
| print(); | |
| return 0; | |
| } |
太空飞行计划问题
问题描述: W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 E={E1,E2,...,Em},和进行这 些实验需要使用的全部仪器的集合 I={I1,I2,...In}。实验 Ej 需要用到的仪器是 I 的子集 RjÕI。 配置仪器 Ik 的费用为 ck 美元。实验 Ej 的赞助商已同意为该实验结果支付 pj 美元。W 教授的 任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才 能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部 费用的差额。
́编程任务: 对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。
́数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 m 和 n。m 是实验数,n 是仪器数。接下来的 m 行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费 用;接着是该实验需要用到的若干仪器的编号。最后一行的 n 个数是配置每个仪器的费用。
́结果输出:
程序运行结束时,将最佳实验方案输出到文件 output.txt 中。第 1 行是实验编号;第 2 行是仪器编号;最后一行是净收益。
输入文件示例
input.txt
2 3
10 1 2
25 2 3
5 6 7
输出文件示例
output.txt
1 2
1 2 3
17
上次修改时间 2017-02-03