2187. 星际转移问题
2026-08-04
题解
由于涉及到天数,不难想到分层图,我们令 (day,i) 表示第 day 天第 i 的点,我们在这个基础上进行网络流建模。
首先,将源点 S 向 (0,0) 连一条容量为 k 的边,从所有 (x,n+1) 向汇点 T 连容量为 +∞ 的边。
然后,我们从所有 (x,y) 向 (x+1,y) 连容量为 +∞ 的边,表示在某个空间站待了一天,再根据车辆的运输,连一些容量为 r 的边。
由于原图随着天数增多,图慢慢变大且运量单调不降,我们可以直接枚举 day,直到流量 ≥k 为止(二分由于需要反复建图,会变慢)。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
struct Ship {
int h , r , id[25];
};
const int N = 1101 * 50 + 10 , M = (N + 1100 + 20 * 1101) + 10;
const int INF = 0x3f3f3f3f;
namespace DSU {
int p[30];
void init() {
for(int i = 0 ; i < 30 ; i ++)
p[i] = i;
}
int find(int x) {
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x , int y) {
x = find(x); y = find(y);
if(x == y) return;
p[x] = y;
}
bool check(int x , int y) {
return find(x) == find(y);
}
}
int n , m , k , S , T;
int h[N] , e[M] , ne[M] , w[M] , idx;
int q[N] , d[N] , cur[N];
Ship ships[30];
void add(int a , int b , int c) {
e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
e[idx] = a , w[idx] = 0 , ne[idx] = h[b] , h[b] = idx ++;
}
bool bfs() {
int hh = 0 , tt = -1;
memset(d , -1 , sizeof d);
q[++ tt] = S; d[S] = 0; cur[S] = h[S];
while(hh <= tt) {
int t = q[hh ++];
for(int i = h[t] ; ~i ; i = ne[i]) {
int v = e[i];
if(d[v] == -1 && w[i]) {
d[v] = d[t] + 1;
cur[v] = h[v];
if(v == T) return true;
q[++ tt] = v;
}
}
}
return false;
}
int find(int u , int limit) {
if(u == T) return limit;
int flow = 0;
for(int i = cur[u] ; ~i ; i = ne[i]) {
cur[u] = i;
int v = e[i];
if(d[v] == d[u] + 1 && w[i]) {
int t = find(v , min(w[i] , limit-flow));
if(!t) d[v] = -1;
flow += t; w[i^1] += t; w[i] -= t;
}
}
return flow;
}
int dinic() {
int r = 0 , flow;
while(bfs()) while((flow = find(S , INF))) r += flow;
return r;
}
int get(int i , int day) {
return day*(n+2) + i;
}
int main() {
scanf("%d%d%d" , &n , &m , &k);
DSU::init(); S = N-2; T = N-1;
memset(h , -1 , sizeof h);
for(int i = 0 ; i < m ; i ++) {
int a , b; scanf("%d%d" , &a , &b);
ships[i].h = a; ships[i].r = b;
for(int j = 0 ; j < b ; j ++) {
int id; scanf("%d" , &id);
if(id == -1) id = n+1;
ships[i].id[j] = id;
if(j) DSU::merge(ships[i].id[j-1] , id);
}
}
if(!DSU::check(0,n+1)) puts("0");
else {
add(S , get(0,0) , k);
add(get(n+1,0) , T , INF);
int day = 1 , res = 0;
while(true) {
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 = ships[i].r;
int a = ships[i].id[(day-1)%r] , b = ships[i].id[day%r];
add(get(a,day-1) , get(b,day) , ships[i].h);
}
res += dinic();
if(res >= k) break;
day ++;
}
printf("%d\n" , day);
}
return 0;
}