「网络流 24 题」星际转移
题解：本题的难点在于问题中涉及到很多天，而对于这种涉及到很多天的问题我们一般用分层图的实现来解决。对于每一天建一层图，然后对于每个飞行器就从前一天向后一天的位置连边容量为飞船容量的边，然后对于每个点从前一天向后一天连边。枚举天数，当最大流大于总人数的时候输出天数

#include <bits/stdc++.h>
#define pb push_back

const int MAXN = 1000000,INF = 1000000;

using namespace std;

int n,m,k,s,t,start,en,e = 2,ans;
int head[MAXN],cur[MAXN],d[MAXN],fa[MAXN];

vector<int>ship[1000];

struct Edge{
    int v,c,f,next;
}edge[MAXN];

inline void addedge(int u,int v,int c)
{
    edge[e] = (Edge){v,c,0,head[u]};head[u] = e++;
    edge[e] = (Edge){u,0,0,head[v]};head[v] = e++;
}

struct node{
    int a,b;
}inf[100];

int getfather(int x){
    if(fa[x] == x) return x;
    return fa[x] = getfather(fa[x]);
}

inline void init()
{
    scanf("%d %d %d",&n,&m,&k);
    int v,last;t = 2000;
    start = n + 1;
    en = n + 2;
    
    for(int i = s;i <= n + 2;i++) fa[i] = i;
    
    for(int i = 1;i <= m;i++)
    {
        scanf("%d %d",&inf[i].a,&inf[i].b);
        for(int j = 1;j <= inf[i].b;j++)
        {
            scanf("%d",&v);
            if(v ==  0) v = n + 1;
            if(v == -1) v = n + 2;
            ship[i].pb(v);
            if(j == 1) last = v;
            else {
                if(getfather(last) != getfather(v)) fa[getfather(v)] = getfather(last);
                
                last = v;
            }
        }    
    }
    addedge(s,start,INF);addedge(en,t,INF);
}

queue<int>Q;
inline bool bfs(){
    memset(d,0,sizeof(d));
    Q.push(s);d[s] = 1;
    while(!Q.empty()){
        int x = Q.front();Q.pop();
        for(int i = head[x];i;i = edge[i].next){
            Edge E = edge[i];
            if(!d[E.v] && E.c > E.f){
                d[E.v] = d[x] + 1;
                Q.push(E.v);
            }
        }
    }
    return d[t] ? true : false;
}

int dfs(int x,int a){
    if(x == t || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        Edge &E = edge[i];
        if(d[E.v] == d[x] + 1 && (f = dfs(E.v,min(a,E.c-E.f))) > 0){
            E.f += f;
            edge[i^1].f -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}

inline int dinic(){
    int flow = 0;
    while(bfs()){
        for(int i = s;i <= t;i++) cur[i] = head[i];
        flow += dfs(s,INF);
    }
    return flow;
}

inline void build(int day){
    for(int i = 1;i <= n + 2;i++) addedge(i+(n+2)*(day-1),i+(n+2)*(day),INF);
    addedge(s,start+(n+2)*(day),INF);addedge(en+(n+2)*(day),t,INF);
    for(int i = 1;i <= m;i++) {
    addedge(ship[i][(day-1)%inf[i].b]+(n+2)*(day-1),ship[i][day%inf[i].b]+(n+2)*(day),inf[i].a);
    }
}

int main()
{
    #ifdef hi_archer
      freopen("input.txt", "r", stdin);
    #endif
    init();

    if(getfather(start) != getfather(en)) printf("0");
    
    else for(int i = 1;;i++){
        build(i);
        ans += dinic();
        if(ans >= k){
        printf("%d\n",i);
        break;
        }
    }
    
    return 0;
}