[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，输出天数

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

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 1000001 6 #define INF 1e9 7 #define min(x, y) ((x) < (y) ? (x) : (y)) 8 9 int n, m, k, s, t, cnt, sum; 10 int f[N], c[N], p[N], b[101][101], dis[N]; 11 int head[N], to[N << 1], next[N << 1], val[N << 1]; 12 13 inline int C(int t, int x) 14 17 18 inline int read() 19 26 27 inline int find(int x) 28 31 32 inline void add(int x, int y, int z) 33 39 40 inline bool bfs() 41 59 } 60 } 61 return 0; 62 } 64 inline int dfs(int u, int maxflow) 65 79 } 80 if(ret ^ maxflow) dis[u] = 1; 81 return ret; 82 } 83 84 int main() 85 105 } 106 } 107 if(find(1) ^ find(2)) 108 112 d = 0; 113 memset(head, 1, sizeof(head)); 114 add(s, 2, k); 115 add(2, s, 0); 116 while(1) 117 124 for(i = 1; i <= m; i++) 125 129 add(C(d, 1), t, INF); 130 add(t, C(d, 1), 0); 131 while(bfs()) sum += dfs(s, INF); 132 if(sum == k) 133 137 } 138 }
View Code

上一篇：[luoguP2870] [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（后缀数组）

下一篇：[POJ1703]Find them, Catch them（并查集）

---

最大流 网络流