翻车笔记_ 星际转移问题 [最大流, 翻车]

一些数据范围小的时间范围可以考虑把点拆成在每一时刻的状态

懵逼的 题目

传送至 Luogu

扯淡的 题解

啊…首先把每个点分成好多个点(敲黑板划重点, 再次强调网络流的裂点)…分成这个空间站在不同时间点的状态, 然后按照题意连边:


按照飞船的飞行路线连边…容量为这个飞船的容量, to的时间点是from的时间点+ 1
别忘了每个点还可以停留人…所以每个点都要向自己在下一时间点的状态连边…


主体就是从时间点0开始连边, 随着时间的增加, 开始给飞船航线周期性的连边和给每个点的滞留连边, 然后跑最大流, 如果最大流量超过了要运送的人数, 返回, 答案就是这时的时间

然后有几个细节…

  1. 因为有一个点被不同时间点分成好几个点…所以不能简单的把地球和月球当做st…应该建一个超级源点 & 汇点, 然后向所有时间的地球 & 月球连边, 容量为INF
  2. 在连边的时候…给每条滞留边连边的时候是要枚举每一个点的…不能仅仅在飞船航线上顺便连上…
  3. 周期性…在飞到航线的最后一后站飞船会返回第一站…而且是可以带着人返回第一站的…不是就瞬移回去了…

然后就没啥了…写就行了…
然后我调了5节课

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXSTA (16 + 1)
#define MAXUSH (20 + 2)
#define MAXANS (50 + 2)
#define MAXN (1000 + 5)
#define MAXM (1000000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(i) (((i - 1) ^ 1) + 1)
#define bh(i, t) (((t) * MAXSTA) + (i))
#define ubh(x) ((x) % MAXSTA)
const int s = 0, moon = 14, t = 15, earth = 16;
using namespace std;
struct edg
{
int from;
int to;
int next;
int cap;
int flow;
edg() {}
edg(int a, int b, int c, int d, int e): from(a), to(b), next(c), cap(d), flow(e) {}
} b[MAXM << 1];
int g[MAXN];
int cntb;

int sta;
int ush;
int npe;
int a[MAXUSH + 5][MAXSTA + 5];
int cap[MAXUSH + 5];
int ans;
int dis[MAXN];
void adn(int, int, int);
void solve();
bool bfs(int);
int dinic(int, int);
int main()
{
scanf("%d%d%d", &sta, &ush, &npe);
for (int i = 1; i <= ush; i++)
{
scanf("%d%d", &cap[i], &a[i][0]);
for (int j = 1; j <= a[i][0]; j++)
{
scanf("%d", &a[i][j]);
if (a[i][j] == -1)
a[i][j] = moon; //
if (!a[i][j])
a[i][j] = earth; //
}
// a[i][0]--;
}
solve();
if (ans < MAXANS)
printf("%d\n", ans);
else
puts("0");
return 0;
}
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap, 0);
g[from] = cntb;
}
void solve()
{
for (int i = 0; i < MAXANS; i++) //
{
adn(bh(moon, i), t, INF);
adn(t, bh(moon, i), 0);
}
for (int i = 0; i < MAXANS; i++) //
{
adn(s, bh(earth, i), INF);
adn(bh(earth, i), s, 0);
}
int maxt = 0;
for (ans = 0; ans < MAXANS; ans++)
{
for (int i = 1; i <= ush; i++)
{
for (int j = 1; j <= a[i][0]; j++) //
{
adn(bh(a[i][j % a[i][0] + 1], ans), bh(a[i][j % a[i][0] + 1], ans + 1), INF);
adn(bh(a[i][j % a[i][0] + 1], ans + 1), bh(a[i][j % a[i][0] + 1], ans), 0);
}
adn(bh(a[i][ans % a[i][0] + 1], ans), bh(a[i][(ans + 1) % a[i][0] + 1], ans + 1), cap[i]);
adn(bh(a[i][(ans + 1) % a[i][0] + 1], ans + 1), bh(a[i][ans % a[i][0] + 1], ans), 0);
}
while (bfs(s))
{
int zl = dinic(s, INF);
maxt += zl;
}
if (maxt >= npe)
{
ans += 2;
return ;
}
}
}
bool bfs(int start)
{
memset(dis, 0, sizeof(dis));
dis[start] = 1;
queue<int> q;
q.push(start);
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && (!dis[b[i].to]))
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
int dinic(int dq, int maxf)
{
if (dq == t || (!maxf))
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[dq] + 1 == dis[b[i].to])
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
maxf -= zl;
re += zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}

/*
2 3 3
1 2 0 2
1 2 1 2
1 2 1 -1

ans: 7

2 2 1
1 3 0 1 2
1 3 1 2 -1

e12e12e12e12
12m12m12m12m

ans: 5

13 20 50
3 5 13 11 2 11 7
4 6 1 10 2 0 9 8
3 4 13 7 5 6
4 7 12 4 8 2 7 8 0
2 2 -1 11
5 3 8 5 11
6 3 12 11 6
6 6 2 13 11 13 8 5
8 6 3 7 12 11 6 6
7 6 7 2 8 11 9 1
8 7 1 11 1 4 4 2 3
6 3 10 6 5
4 4 2 0 3 9
4 5 8 5 7 5 -1
8 3 5 1 2
2 5 6 8 5 8 -1
8 3 10 11 4
2 7 1 2 0 5 0 13 11
5 7 10 3 7 8 9 2 3
4 4 13 1 8 0

ans: 29
*/

By 菜鸡 Cansult