最大流判定（星际转移问题）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include 
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int    long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 1e5 + 10,M=2e5+10, INF = 0x3f3f3f3f;

int n,m,k,S,T;
int h[N],ne[M],e[M],f[M],idx;
int cur[N],d[N],q[N];

void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
    e[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}



struct node
{
    int h,r,id[30];
}ship[30];
int par[30];

int find(int x)
{
    if(x==par[x]) return x;
    return par[x]=find(par[x]);
}

int find(int u,int limit)
{
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}
 

 bool bfs()
 {
    int hh=0,tt=0;
    memset(d,-1,sizeof(d));
    cur[S]=h[S],q[0]=S,d[S]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
 }


int get(int a,int b)
{
    return b*(n+2)+a;
}



int dinic()
{
    int r=0,flow;
    while(bfs()) while(flow=find(S,INF)) r+=flow;
    return r;
}




void solve()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof(h));
    S=N-1,T=N-2;
    for(int i=0;i<=n+1;i++) par[i]=i;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        ship[i]={a,b};
        for(int j=0;j<b;j++)
        {
            int x;
            cin>>x;
            if(x==-1) x=n+1;
            ship[i].id[j]=x;
            if(j>=1)
            {
                par[find(x)]=find(ship[i].id[j-1]);
            }
        }
    }
    if(par[find(0)]!=par[find(n+1)])
    {
        cout<<0<<endl;
        return;
    }
    add(S,get(0,0),k);
    add(get(n+1,0),T,INF);
    int day=1;
    int res=0;
    while(true)
    {
        add(get(n+1,day),T,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 md1=ship[i].r;
            add(get(ship[i].id[(day-1)%md1],day-1),get(ship[i].id[day%md1],day),ship[i].h);
        }
        res+=dinic();
        if(res>=k)
        {
            cout<<day<<endl;
            return;
        }
        day++;
    }
}



signed main() {
std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    //#ifdef LOCAL
    //freopen("data.in.txt","r",stdin);
    //freopen("data.out.txt","w",stdout);
    //#endif
    int __ = 1;
    //cin>>__;
    while (__--)
        {
            solve();
        }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173