[luoguP2754] 星际转移问题（最大流）

传送门

不同的时间每个飞船所在的地点不同，给我们启示按照时间构建分层图。

同一个地点 x <x, day_{i - 1}>-> <x, day_i>连一条容量为 INF 的边，因为人们可以在一个地点等待

艘飞船的路径如果 a 的下一站是 b，那么 <a, day_{i - 1}> -> <b, day_i> 连一条容量为该飞船容量的边，表示可以 a 坐飞船到 b

增加超级源点 s，s 和地球连一条容量为 k 的边

增加超级汇点 t，月球的每一天都和 t 连一条容量为 INF 的边

枚举天数，跑最大流，直到 max_flow == k，输出天数

对于判断是否能到达，用并查集判断连通性

——代码

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 1000001

 #define INF 1e9

 #define min(x, y) ((x) < (y) ? (x) : (y))

 int n, m, k, s, t, cnt, sum;

 int f[N], c[N], p[N], b[][], dis[N];

 int head[N], to[N << ], next[N << ], val[N << ];

 inline int C(int t, int x)

 {

     return t * (n + ) + x;

 } 

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int find(int x)

 {

     return x == f[x] ? x : f[x] = find(f[x]);

 }

 inline void add(int x, int y, int z)

 {

     to[cnt] = y;

     val[cnt] = z;

     next[cnt] = head[x];

     head[x] = cnt++;

 }

 inline bool bfs()

 {

     int i, u, v;

     std::queue <int> q;

     memset(dis, -, sizeof(dis));

     q.push(s);

     dis[s] = ;

     while(!q.empty())

     {

         u = q.front(), q.pop();

         for(i = head[u]; i ^ -; i = next[i])

         {

             v = to[i];

             if(val[i] && dis[v] == -)

             {

                 dis[v] = dis[u] + ;

                 if(v == t) return ;

                 q.push(v);

             }

         }

     }

     return ;

 }

 inline int dfs(int u, int maxflow)

 {

     if(u == t) return maxflow;

     int v, d, ret = ;

     for(int i = head[u]; i ^ -; i = next[i])

     {

         v = to[i];

         if(val[i] && dis[v] == dis[u] + )

         {

             d = dfs(v, min(val[i], maxflow - ret));

             ret += d;

             val[i] -= d;

             val[i ^ ] += d;

             if(ret == maxflow) return ret;

         }

     }

     if(ret ^ maxflow) dis[u] = -;

     return ret;

 }

 int main()

 {

     int i, j, x, y, d;

     n = read();

     m = read();

     k = read();

     s = N - , t = N - ;

     for(i = ; i <= n + ; i++) f[i] = i;

     for(i = ; i <= m; i++)

     {

         c[i] = read();

         p[i] = read();

         for(j = ; j < p[i]; j++)

         {

             b[i][j] = read() + ;

             if(j)

             {

                 x = find(b[i][j - ]);

                 y = find(b[i][j]);

                 if(x ^ y) f[x] = y;

             }

         }

     }

     if(find() ^ find())

     {

         printf("0\n");

         return ;

     }

     d = ;

     memset(head, -, sizeof(head));

     add(s, , k);

     add(, s, );

     while()

     {

         d++;

         for(i = ; i <= n + ; i++)

         {

             add(C(d - , i), C(d, i), INF);

             add(C(d, i), C(d - , i), );

         }

         for(i = ; i <= m; i++)

         {

             add(C(d - , b[i][(d - ) % p[i]]), C(d, b[i][d % p[i]]), c[i]);

             add(C(d, b[i][d % p[i]]), C(d - , b[i][(d - ) % p[i]]), );

         }

         add(C(d, ), t, INF);

         add(t, C(d, ), );

         while(bfs()) sum += dfs(s, INF);

         if(sum == k)

         {

             printf("%d\n", d);

             return ;

         }

     }

 }

巴特西

[luoguP2754] 星际转移问题（最大流）

最新文章

热门文章