刚开始想费用流的我真是思博
发现最终的答案只取决于最后到达的那一批人到达的时间，于是发觉这应该是一个最大流
显然我们需要把每一个太空站按照时间拆点，之后上一个时间向下一个时间连边，容量无限，之后对于航线我们就直接在不同时间连不同的边就好了
最后的答案就是我们拆出来的最大的时间
应该可以二分的，但是动态加边看起来更加科学
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=1000005;
const int inf=99999999;
inline int read() {
char c=getchar();int x=0,r=1;
while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return r*x;
}
std::queue<int> q;
struct E{int v,nxt,f;}e[maxn];
int d[maxn],head[maxn],cur[maxn];
int a[21][21],num=1,n,m,k,now[21],R,cnt,S,T;
int fa[21],sz[21],tot[21],t[21],pre[21],p[21];
int find(int x) {if(x==fa[x]) return x;return fa[x]=find(fa[x]);}
inline void merge(int x,int y) {
int xx=find(x),yy=find(y);
if(xx==yy) return;
if(sz[xx]>sz[yy]) fa[yy]=xx,sz[xx]+=sz[yy];
else fa[xx]=yy,sz[yy]+=sz[xx];
}
inline void C(int x,int y,int f) {
e[++num].v=y;e[num].nxt=head[x];
e[num].f=f;head[x]=num;
}
inline void add(int x,int y,int f) {C(x,y,f),C(y,x,0);}
inline int BFS() {
for(re int i=S;i<=R;i++) d[i]=0,cur[i]=head[i];
d[S]=1,q.push(S);
while(!q.empty()) {
int kk=q.front();q.pop();
for(re int i=head[kk];i;i=e[i].nxt)
if(!d[e[i].v]&&e[i].f)
d[e[i].v]=d[kk]+1,q.push(e[i].v);
}
return d[T];
}
int dfs(int x,int now) {
if(x==T||!now) return now;
int flow=0,ff;
for(re int& i=cur[x];i;i=e[i].nxt)
if(d[e[i].v]==d[x]+1) {
ff=dfs(e[i].v,min(e[i].f,now));
if(ff<=0) continue;
now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;
if(!now) break;
}
return flow;
}
int main() {
n=read(),m=read(),k=read();
for(re int i=0;i<=n+1;i++) sz[i]=1,fa[i]=i;
for(re int i=1;i<=m;i++) {
t[i]=read();tot[i]=read();
for(re int j=1;j<=tot[i];j++) {
a[i][j]=read();
if(a[i][j]==-1) a[i][j]=n+1;
}
for(re int j=1;j<tot[i];j++)
merge(a[i][j],a[i][j+1]);
for(re int j=1;j<=tot[i];j++) a[i][j]++;
a[i][tot[i]+1]=a[i][1];
}
if(find(0)!=find(n+1)) {puts("0");return 0;}
S=0;T=R=n+3;
int ans=0;
for(re int i=1;i<=n+2;i++) pre[i]=i;
for(re int i=1;i<=n+2;i++) now[i]=++R;
add(S,1,k);add(now[n+2],T,k);
for(re int i=1;i<=m;i++) {
add(pre[a[i][1]],now[a[i][2]],t[i]);
p[i]=2;
}
while(BFS()) ans+=dfs(S,inf);cnt=1;
for(;ans<k;++cnt) {
for(re int i=1;i<=n+2;i++)
add(pre[i],now[i],inf),pre[i]=now[i];
for(re int i=1;i<=n+2;i++) now[i]=++R;
add(now[n+2],T,k);
for(re int i=1;i<=m;i++) {
if(p[i]>tot[i]) p[i]=1;
add(pre[a[i][p[i]]],now[a[i][p[i]+1]],t[i]);
p[i]++;
}
while(BFS()) ans+=dfs(S,inf);
}
printf("%d
",cnt);
return 0;
}