星际转移问题

解题思路

本题的主要题意就是，在 $0$ 号点和 $n+1$ 号点之间有 $n$ 个中间点，有 $m$ 个公交车在所有点之间不断的循环走各自的路线，每个公交车走到下一个站点都需要 $1$ 天的时间，问最短需要几天时间能将 $k$ 个人从 $0$ 号点 送到 $n+1$ 号点。

首先对于当前情况是否有解，其实就是看一下 $0$ 号点和 $n+1$ 号点是否连通，可以用并查集，bfs，dfs来判断。

如果有解，那么我们应该如何求最少需要的天数呢？

我们其实需要判断多少天能将所有人运到 $n+1$ 号点，即判断用 $day$ 天能否将人运到 $n+1$ 号点。由于网络流中只有流量的概念，并没有距离（天数）的概念，因此我们需要引入分层图，使得网络流中加入一个距离（天数）的概念。

我们可以从第 $0$ 天开始将整个流网络分成 $day+1$ 天。由于最终一定要到达某个空间站，所以本题可以将所有空间站作为点，把所有公交车作为边来建图。每个状态 $(i,~j)$ 表示第 $j$ 天的第 $i$ 个空间站的状态（共 $n+2$ 个空间站）。

对应的某些状态之间存在转移方式，也就是它们之间的边，我们直接根据人能走的合法的移动路线来建边即可。

流网络还需要一个源点和一个汇点。最开始所有人都在第 $0$ 天的第 $0$ 个空间站，所以从源点只能向 $(0,~0)$ 连一条容量为 $k$ 边。而汇点则是你不管第几天，只要能到第 $n+1$ 个空间站，就能到汇点，所以应该从每一天的第 $n+1$ 个空间站，即 $(n+1, ~?)$ 向汇点连一条容量为 $+\infty$ 的边。

然后我们还需要考虑一下空间站之间的边，即人能走的合法的移动方式有哪些。

一种方式是坐公交车，从一个站点到另一个站点，那么就可以根据每辆公交车的路线来建边，假设某一辆公交车最开始在第 $0$ 个站点，然后依次开往第 $2$ 个站点，再开往第 $5$ 个站点，那么先从第 $0$ 天的第 $0$ 个站点向第 $1$ 天的第 $2$ 个站点连一条边，再从第 $1$ 天的第 $2$ 个站点向第 $3$ 天的第 $5$ 个站点连一条边，容量都是这个公交车的人数上限，其他路线依次类推。

另一种方式就是每个人都是可以呆在空间站里不走的，因此每一天的每个空间站都可以向后一天的同一个空间站连一条容量为 $+\infty$ 的边。

综上所述，我们就将整个流网络建立起来了。

接下来还需要证明一下原问题的可行解能否对应流网络的可行流。可以发现可行解中每个人行走的方式都能对应到流网络中的某一条边，只需要根据该方式移动的人数来设置对应的边的流量，就能得到对应的可行流，反过来同理。

因此只要当前流网络的最大流的流量 $\geq k$，说明我们能在 $day$ 天之内移动 $k$ 个人，否则说明 $day$ 天不合法。

剩下的问题就是我们如何去枚举 $day$，首先是可以二分枚举的，但是本题比较特殊，可以发现站点数量是和 $day$ 成正比的，$day$ 每增加 $1$，就会多一排站点。而且随着 $day$ 的增加，网络只会不断变多而不会减少。并且最大流算法是可以在当前网络上继续增广，因此本题中从小到大枚举 $day$ 其实是比二分更好的。

最终得出整个算法，我们只需要从 $1$ 开始枚举 $day$，$1$ 不行就 $2$，每次 $day+1$ 就多加一排点，再进行增广，直到最大流的流量 $\geq k$ 为止。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1101 * 22 + 10, M = (N + 1100 + 13 * 1101) * 2 + 10, INF = 0x3f3f3f3f;

int n, m, k, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
int p[25]; //并查集

struct Ship
{
    int h, r, id[25]; //人数上限、停靠站点数、停靠的站点
}ships[25]; //存储所有船

int find(int x) //循环 x 的根节点
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int get(int i, int j) //为第 j 天的第 i 个空间站的这个状态设置一个编号
{
    return j * (n + 2) + i;
}

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 = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往汇点最多能传输多少流量，传输上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //dinic 求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    memset(h, -1, sizeof h); //初始化邻接表

    S = N - 2, T = N - 1; //源点、汇点

    for(int i = 0; i < 25; i++) p[i] = i; //初始化并查集

    //接收所有太空船
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d", &ships[i].h, &ships[i].r);

        for(int j = 0; j < ships[i].r; j++)
        {
            int x;
            scanf("%d", &x);
            if(x == -1) x = n + 1; //特判，终点 -1 改为 n+1

            ships[i].id[j] = x; //该公交车当前天到达的站点

            if(j) //将路线经过的所有点合并
            {
                int a = ships[i].id[j - 1]; //该公交车前一条到达的站点
                p[find(a)] = find(x); //合并
            }
        }
    }

    //如果 0 号点和 n+1 号点不在一个集合，说明无解
    if(find(0) != find(n + 1)) puts("0");
    else //否则说明有解
    {
        add(S, get(0, 0), k); //从源点向 (0, 0) 连一条容量为 k 的边
        add(get(n + 1, 0), T, INF); //从第 0 天的 n + 1 号点向汇点连一条容量为 INF 的边

        int day = 1; //记录当前所在的天数
        int res = 0; //记录第 day 天之前已经运到 n + 1 号点的人数
        while(true)
        {
            //每次 day + 1，需要加入新一排的点和边

            add(get(n + 1, day), T, INF); //从当前天的 n + 1 号点向汇点连一条容量为 INF 的边

            //从每一个点的前一天向当前天连一条容量为 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 a = ships[i].id[(day - 1) % ships[i].r]; //该辆公交车前一天所在的站点
                int b = ships[i].id[day % ships[i].r]; //该辆公交车当前天所在的站点
                //从前一天所在的站点向当前天所在的站点连一条容量为该辆公交车人数上限的边
                add(get(a, day - 1), get(b, day), ships[i].h);
            }

            res += dinic(); //累加第 day 能多运到 n + 1 号点的人数
            if(res >= k) break; //如果第 day 天已经能运 k 个人，说明找到最少天数，跳出循环
            day++; //到这说明当前 day 天无法运 k 个人，day + 1
        }
        printf("%d\n", day);
    }
    return 0;
}