人在各个太空站流动，所以显然的网络流模型
因为不同时间能走的边不同，所以显然按时间拆点
但是因为不知道要多少时间，所以要枚举时间，动态拆点
每一点向下一个时间的同一点连流量为 $INF$ 的边，表示时间的转移
因为知道时间，所以可以求出每站的下一站，流量显然就是对应太空船的容量
每多一时间就拆一波点
不用每次都把图重建，每次在残量网络上继续跑就好了
当最大流大于或等于总人数时就的时间就是答案
用并查集判断源点和汇点是否联通，判断是否有解
时间复杂度$O(能过)$，空间复杂度玄学
跑得还挺快...
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,INF=1e9+7; int fir[N],from[N<<2],to[N<<2],val[N<<2],cntt=1; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } int n,m,K,S,T,tot; int dep[N]; queue <int> q; bool BFS() { for(int i=0;i<=tot;i++) dep[i]=0; q.push(S); dep[S]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; q.push(v); } } return dep[T] ? 1 : 0; } int DFS(int x,int mif) { if(x==T||!mif) return mif; int fl=0,res=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1) continue; if( res=DFS(v,min(mif,val[i])) ) { fl+=res; mif-=res; val[i]-=res; val[i^1]+=res; if(!mif) break; } } return fl; } //以上最大流模板 struct Ship{//存太空船的信息 int sz,t;//容纳人数和经过站点的数量 vector <int> v;//太空船经过的太空站 }p[233]; int fa[N];//并查集 inline int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); } int ans,mxf; int main() { n=read()+2,m=read(),K=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { p[i].sz=read(),p[i].t=read(); for(int j=1;j<=p[i].t;j++) { int a=read(); if(a==-1) a=n; if(a==0) a=n-1; p[i].v.push_back(a); } for(int j=1;j<p[i].t;j++) { int xa=find(p[i].v[j]),ya=find(p[i].v[0]); if(xa!=ya) fa[xa]=ya; } } if(find(n-1)!=find(n)) { printf("0"); return 0; } S=n-1; tot=n; while(1)//枚举时间 { for(int i=1;i<=n;i++) add(tot-n+i,tot+i,INF); for(int i=1;i<=m;i++) add(tot-n+p[i].v[ ans%p[i].t ],tot+p[i].v[ (ans+1)%p[i].t ],p[i].sz); tot+=n; T=tot; ans++; while(BFS()) mxf+=DFS(S,INF); if(mxf>=K) break; } printf("%d",ans); return 0; }