本文主要是介绍2187. 星际转移问题（最大流，最大流判定，分层图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
活动 - AcWing
由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。
于是在月球上建立了新的绿地，以便在需要时移民。
令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。
现有 n 个太空站（编号 1∼n）位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。
每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i] 个人。
每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4) 表示该太空船将周期性地停靠太空站 134134134…。
每一艘太空船从一个太空站驶往任一太空站耗时均为 1。
人们只能在太空船停靠太空站(或月球、地球)时上、下船。
初始时所有人全在地球上，太空船全在初始站，即行驶周期中的第一个站。
试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。
输入格式
第 1 行有 3 个正整数 n（太空站个数），m（太空船个数）和 k（需要运送的地球上的人的个数）。
接下来的 m 行给出太空船的信息。第 i+1 行说明太空船 pi。第 1 个数表示 pi 可容纳的人数 H[pi]；第 2 个数表示 pi 一个周期停靠的太空站个数 r；随后 r 个数是停靠的太空站的编号 (Si1,Si2,…,Sir)，地球用 0 表示，月球用 −1 表示。
时刻 00 时，所有太空船都在初始站，然后开始运行。
在时刻 1，2，3… 等正点时刻各艘太空船停靠相应的太空站。
人只有在 0,1,2… 等正点时刻才能上下太空船。
输出格式
输出让所有人尽快地全部转移到月球上的最短用时。
如果无解，则输出 0。
数据范围
1≤n≤13,
1≤m≤20,
1≤k≤50,
1≤r≤n+2,
输入样例：
2 2 1
1 3 0 1 2
1 3 1 2 -1
输出样例：
5解析：
这道题可以枚举天数，建立分成图，每一天就是一层。
这道题不能使用二分，因为建立分层图是根据天数来建的，二分的话天数会波动；而如果枚举天数的话由于每次天数增加 1 ，因此图每次多一层，而且最大流算法可以在之前的残留网络的基础上运算，所以直接在上一次的残留网络上加一层即可。因此枚举天数能使算法更简洁，高效。
#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 = 1101 * 50 + 10, M = (N + 1100 + 20 * 1101) + 10, INF = 0x3f3f3f3f;
int n, m, k, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
struct Ship {int h, r, id[30];
}ship[30];
int p[30];int find(int x) {if (p[x] == x)return x;return p[x] = find(p[x]);
}int get(int x, int day) {return day * (n + 2) + x;
}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;
}int main() {cin >> n >> m >> k;memset(h, -1, sizeof h);S = N - 2, T = N - 1;for (int i = 0; i < 30; i++)p[i] = i;for (int i = 0; i < m; i++) {scanf("%d%d", &ship[i].h, &ship[i].r);for (int j = 0; j < ship[i].r; j++) {int id;scanf("%d", &id);if (id == -1)id = n + 1;ship[i].id[j] = id;if (j) {int x = ship[i].id[j - 1];p[find(x)] = find(id);}}}if (find(0) != find(n + 1))cout << 0 << endl;else {int day = 1, ret = 0;add(S, get(0, 0), k);add(get(n + 1, 0), T, INF);while (1) {add(get(n + 1, day), T, INF);for (int i = 0; i <= n + 1; i++) {add(get(i, day - 1), get(i, day), INF);}for (int i = 0; i < m; i++) {int r = ship[i].r;int a = ship[i].id[(day - 1) % r], b = ship[i].id[(day) % r];add(get(a, day - 1), get(b, day ), ship[i].h);}ret += dinic();if (ret >= k)break;day++;}cout << day << endl;}return 0;
}这篇关于2187. 星际转移问题（最大流，最大流判定，分层图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
