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

懵逼的 题目

传送至 Luogu

扯淡的 题解

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


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


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

然后有几个细节…

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

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

沙茶的 代码

#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