本文主要是介绍2176. 太空飞行计划问题（最小割，最大权闭合图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
活动 - AcWing
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 开始。
输出格式
将最佳实验方案输出。
第 1 行是实验编号；
第 2 行是仪器编号；
最后一行是净收益。
如果最佳方案不唯一，则输出任意一种均可。
数据范围
1≤m,n≤50
所有仪器费用以及赞助费用均不超过 100。
输入样例：
2 3
10 1 2
25 2 3
5 6 7
输出样例：
1 2
1 2 3
17解析：
本题给了很多实验，完成每个实验能获得一定的收益，还有很多器材，每个实验需要对应的一些器材，每个器材都有一个花费。
可以发现想完成每个实验都需要购买对应的器材，如果将所有器材的权值设置成负数，所有实验的权值设置成正数，如果将所有实验向对应的器材连一条边，那么可以发现任何一个原问题的可行方案都会对应到图中的一个闭合子图。
因此本题求的最大净收益其实就是图中的最大权闭合子图，因此可以用求最大权闭合子图的方法来求，从源点向所有实验连一条容量是收益的边，从所有器材向汇点连一条容量是花费的边，从所有实验向对应的器材连一条容量是 +∞ 的边。
因此本题是经典的最大权闭合子图问题的应用，最大权闭合子图 = 正权点的权值和 − 最小割。（最大权闭合子图定理）
本题还要输出方案，可以从最小割中推出最大权闭合子图，就是 S−{s}，即所有从源点能搜到的点（除源点）。
作者：小小_88
链接：https://www.acwing.com/solution/content/132894/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
————————————————————————————————————————————
最大权闭合图详解：最大权闭合子图的基本概念 - AcWing
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e2 + 10, M = (50*50+N) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}bool bfs() {int hh = 0, tt = 0;memset(d, -1, sizeof d);q[0] = S, d[S] = 0, cur[S] = h[S];while (hh <= tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] == -1 && f[i]) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}int find(int u, int limit) {if (u == T)return limit;int flow = 0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i]) {int t = find(j, min(f[i], limit - flow));if (!t)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}int dinic() {int ret = 0, flow;while (bfs())while (flow = find(S, INF))ret += flow;return ret;
}void dfs(int u) {st[u] = 1;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j] && f[i])dfs(j);}
}int main() {cin >> m >> n;getchar();memset(h, -1, sizeof h);S = 0, T = n + m + 1;int tot = 0;for (int i = 1; i <= m; i++) {int w, id;string line;getline(cin, line);stringstream ssin(line);ssin >> w;tot += w;add(S, i, w);while (ssin >> id)add(i, id + m, INF);}for (int i = 1, a; i <= n; i++) {scanf("%d", &a);add(i + m, T, a);}int ret = dinic();dfs(S);for (int i = 1; i <= m; i++) {if (st[i])printf("%d ", i);}cout << endl;for (int i = m + 1; i <= n + m; i++) {if (st[i])printf("%d ", i-m);}cout << endl;cout << tot - ret << endl;return 0;
}
这篇关于2176. 太空飞行计划问题（最小割，最大权闭合图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
