## [网络流 24 题](https://www.luogu.com.cn/problem/list?tag=332) 难度从小到大，没写完是因为剩下的我还不会贺。 ### [P4011 孤岛营救问题](https://www.luogu.com.cn/problem/P4011) #### 题意 给你一个 $n\times m$ 的迷宫，两个格子之间会有墙或者门，门需要对应的钥匙，墙不能走，在给你每个钥匙的位置，问从 $(1,1)$ 到 $(n,m)$ 的最短路。 #### 题解 这和网络流貌似毫无关系，实际也不用网络流。 每次移动代价为 $1$，考虑 $\text{01BFS}$ ，钥匙个数很小，进行状压，每次计算到 $(i,j)$ 时，拥有的钥匙状态为 $k$，的最小距离。 时间复杂度：$O(nm2^p)$ #### 代码 ```c++ #include <cstdio> #include <cctype> #include <queue> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=x=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int dx[4]={0, 0, -1, 1}; const int dy[4]={-1, 1, 0, 0}; const int N=12; int n, m, p, k, s, e[N][N][N][N], cnt[N][N], key[N][N][N], g[N][N]; bool vis[N][N][1<<N]; struct node { int x, y, k, d; }; int bfs(int sx, int sy) { queue<node> q; q.push({sx, sy, g[sx][sy], 0}); vis[sx][sy][g[sx][sy]]=1; while (!q.empty()) { int x=q.front().x, y=q.front().y, d=q.front().d, k=q.front().k; q.pop(); if (x==n && y==m) return d; for (int i=0; i<4; i++) { int X=x+dx[i], Y=y+dy[i], wall=e[x][y][X][Y]; if (X<1 || X>n || Y<1 || Y>m || wall<0 || (wall && !(k&(1<<wall-1)))) continue; int nxt=k|g[X][Y]; if (vis[X][Y][nxt]) continue; q.push({X, Y, nxt, d+1}); vis[X][Y][nxt]=1; } } return -1; } int main() { n=read(), m=read(), p=read(), k=read(); while (k--) { int x1=read(), y1=read(), x2=read(), y2=read(), g=read(); e[x1][y1][x2][y2]=e[x2][y2][x1][y1]=g ? g : -1; } s=read(); while (s--) { int x=read(), y=read(), q=read(); key[x][y][++cnt[x][y]]=q; } for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) for (int k=1; k<=cnt[i][j]; k++) g[i][j]|=(1<<key[i][j][k]-1); printf("%d\n", bfs(1, 1)); return 0; } ``` ### [P2756 飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756) #### 题意 给你一个二分图，输出最大匹配的方案 #### 题解 显然可以用匈牙利算法，而且方案在做的时候已经记录好了，很简单。 但是用网络流显然会快很多，但是怎么记录方案呢？ 我们发现，一条边如果取了，那么它的剩余容量一定会变成 $0$，最后枚举每条边，判断如果剩余容量为 $0$，输出即可。 #### 代码 ```c++ int main() { n=read(), m=read(), s=m+1, t=m+2; for (int i=1; i<=n; i++) add(s, i, 1), add(i, s, 0); for (int i=n+1; i<=m; i++) add(i, t, 1), add(t, i, 0); while (x=read(), y=read(), ~x) add(x, y, 1), add(y, x, 0); int maxflow=0, flow; while (bfs()) { while (flow=dinic(s, 1e9)) maxflow+=flow; } printf("%d\n", maxflow); for (int i=1; i<=n; i++) for (int j=head[i]; j; j=nxt[j]) if (to[j]!=s && val[j]==0) printf("%d %d\n", i, to[j]); return 0; } ``` ### [P2774 方格取数问题](https://www.luogu.com.cn/problem/P2774) #### 题意 $n\times m$ 个带权方格，取任意多个，不能取相邻两个，求获得的最大权值和。 #### 题解 我们可以考虑先取完所有方格，再不断的删去方格，直到合法为止。 显然，相邻的方格不能同时取，他们的横坐标和纵坐标有且仅有一个相差 $1$，它们的坐标和的奇偶性不同。 我们可以按照坐标和的奇偶性把所有方格分成 $2$ 部分，两个点连边代表他们不能同时取，即相邻。 这样就构成了一张二分图，我们把源点向左边的点连边，右边的点向汇点连边，边权为点权，左边和右边的点相邻就连边，边权为 $\inf$。 一个点如果取，代表源点可以到它或它可以到汇点，如果不去，这条边就不能选。 这样，如果源点到汇点联通，代表左边的点和右边的点一定同时取了，所以我们只要让图不连通，求最小割即可。 因为我们把中间的边权设成了 $\inf$，所以一定删掉，所以不会影响答案。 #### 代码 ```c++ int p(int x, int y) {return (x-1)*m+y;} int main() { n=read(), m=read(); s=n*m+1, t=n*m+2; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { int x=read(); ans+=x; if ((i+j)&1) { if (i>1) add(p(i, j), p(i-1, j), 1e9), add(p(i-1, j), p(i, j), 0); if (i<n) add(p(i, j), p(i+1, j), 1e9), add(p(i+1, j), p(i, j), 0); if (j>1) add(p(i, j), p(i, j-1), 1e9), add(p(i, j-1), p(i, j), 0); if (j<m) add(p(i, j), p(i, j+1), 1e9), add(p(i, j+1), p(i, j), 0); add(s, p(i, j), x), add(p(i, j), s, 0); } else add(p(i, j), t, x), add(t, p(i, j), 0); } int flow; while (bfs()) while (flow=dinic(s, 1e9)) ans-=flow; printf("%d\n", ans); return 0; } ``` ### [P3355 骑士共存问题](https://www.luogu.com.cn/problem/P3355) #### 题意 在一个 $n\times n$ 的国际象棋棋盘中有些障碍，最多可以放几匹马，使得他们互不攻击 #### 题解 我们发现，和上面的一题十分像。 两个点不能同时取时，它们的坐标和的奇偶性不同。 连边方式不同，障碍物不连边，其他的和上面一样就好了！ #### 代码 ```c++ const int dx[8]={-2, -2, -1, -1, 1, 1, 2, 2}; const int dy[8]={-1, 1, -2, 2, -2, 2, -1, 1}; int p(int x, int y) {return (x-1)*n+y;} int main() { n=read(), m=read(), s=n*n+1, t=n*n+2; for (int i=1; i<=m; i++) { int x=read(), y=read(); f[x][y]=1; } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { if (f[i][j]) continue; if ((i+j)&1) { for (int k=0; k<8; k++) { int x=i+dx[k], y=j+dy[k]; if (x<1 || x>n || y<1 || y>n || f[i][j]) continue; add(p(i, j), p(x, y), 1e9); add(p(x, y), p(i, j), 0); } add(s, p(i, j), 1), add(p(i, j), s, 0); } else add(p(i, j), t, 1), add(t, p(i, j), 0); } int maxflow=0, flow; while (bfs()) while (flow=dinic(s, 1e9)) maxflow+=flow; printf("%d\n", n*n-m-maxflow); return 0; } ``` #### [P2754 [CTSC1999]家园 / 星际转移问题](https://www.luogu.com.cn/problem/P2754) #### 题意 自己看题吧 #### 题解 数据范围特别小。 我们可以按时间分层，每个节点记录了天数和位置，再考虑连边。 首先每一天每个人可以在当前点不走，即从前一天的这个点到今天的这个点连一条边，边权无限。 对于每个路线，可以从前一天的这个点向今天到达的点连边，边权为飞船最大承载量，即最多这么多人可以走这条路。 当然，还要从超级源点向每一天的地球连边，每一天的月球向汇点连边。 枚举天数，在前一天的残量网络上跑网络流。 如果到达汇点的人数满足了，说明当前天可以到达。 如果很多天还不够，什么无解。 当然，无解也可以用并查集来判断，一个航道能到达的所有点显然可以互相到达，在同一个集合中，如果地球和月球不在同一个集合中，说明无解 #### 代码 ```c++ void ins(int x, int y, int z) {add(x, y, z); add(y, x, 0);} int main() { n=read()+2, m=read(), k=read(); for (int i=1; i<=m; i++) { h[i]=read(), r[i]=read(); for (int j=0; j<r[i]; j++) a[i][j]=read()+2; } while (day<500) { ins(s, day*n+2, 1e9); ins(day*n+1, t, 1e9); if (day) { for (int i=1; i<=n; i++) ins((day-1)*n+i, day*n+i, 1e9); for (int i=1; i<=m; i++) ins((day-1)*n+a[i][(day-1)%r[i]], day*n+a[i][day%r[i]], h[i]); } int flow=0; while (bfs()) while (flow=dinic(s, 1e9)) sum+=flow; if (sum>=k) break; day++; } printf("%d\n", day%500); return 0; } ``` ### 未完待续......（不会了，不想学网络流了qwq） Loading... ## [网络流 24 题](https://www.luogu.com.cn/problem/list?tag=332) 难度从小到大，没写完是因为剩下的我还不会贺。 ### [P4011 孤岛营救问题](https://www.luogu.com.cn/problem/P4011) #### 题意 给你一个 $n\times m$ 的迷宫，两个格子之间会有墙或者门，门需要对应的钥匙，墙不能走，在给你每个钥匙的位置，问从 $(1,1)$ 到 $(n,m)$ 的最短路。 #### 题解 这和网络流貌似毫无关系，实际也不用网络流。 每次移动代价为 $1$，考虑 $\text{01BFS}$ ，钥匙个数很小，进行状压，每次计算到 $(i,j)$ 时，拥有的钥匙状态为 $k$，的最小距离。 时间复杂度：$O(nm2^p)$ #### 代码 ```c++ #include <cstdio> #include <cctype> #include <queue> using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=x=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int dx[4]={0, 0, -1, 1}; const int dy[4]={-1, 1, 0, 0}; const int N=12; int n, m, p, k, s, e[N][N][N][N], cnt[N][N], key[N][N][N], g[N][N]; bool vis[N][N][1<<N]; struct node { int x, y, k, d; }; int bfs(int sx, int sy) { queue<node> q; q.push({sx, sy, g[sx][sy], 0}); vis[sx][sy][g[sx][sy]]=1; while (!q.empty()) { int x=q.front().x, y=q.front().y, d=q.front().d, k=q.front().k; q.pop(); if (x==n && y==m) return d; for (int i=0; i<4; i++) { int X=x+dx[i], Y=y+dy[i], wall=e[x][y][X][Y]; if (X<1 || X>n || Y<1 || Y>m || wall<0 || (wall && !(k&(1<<wall-1)))) continue; int nxt=k|g[X][Y]; if (vis[X][Y][nxt]) continue; q.push({X, Y, nxt, d+1}); vis[X][Y][nxt]=1; } } return -1; } int main() { n=read(), m=read(), p=read(), k=read(); while (k--) { int x1=read(), y1=read(), x2=read(), y2=read(), g=read(); e[x1][y1][x2][y2]=e[x2][y2][x1][y1]=g ? g : -1; } s=read(); while (s--) { int x=read(), y=read(), q=read(); key[x][y][++cnt[x][y]]=q; } for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) for (int k=1; k<=cnt[i][j]; k++) g[i][j]|=(1<<key[i][j][k]-1); printf("%d\n", bfs(1, 1)); return 0; } ``` ### [P2756 飞行员配对方案问题](https://www.luogu.com.cn/problem/P2756) #### 题意 给你一个二分图，输出最大匹配的方案 #### 题解 显然可以用匈牙利算法，而且方案在做的时候已经记录好了，很简单。 但是用网络流显然会快很多，但是怎么记录方案呢？ 我们发现，一条边如果取了，那么它的剩余容量一定会变成 $0$，最后枚举每条边，判断如果剩余容量为 $0$，输出即可。 #### 代码 ```c++ int main() { n=read(), m=read(), s=m+1, t=m+2; for (int i=1; i<=n; i++) add(s, i, 1), add(i, s, 0); for (int i=n+1; i<=m; i++) add(i, t, 1), add(t, i, 0); while (x=read(), y=read(), ~x) add(x, y, 1), add(y, x, 0); int maxflow=0, flow; while (bfs()) { while (flow=dinic(s, 1e9)) maxflow+=flow; } printf("%d\n", maxflow); for (int i=1; i<=n; i++) for (int j=head[i]; j; j=nxt[j]) if (to[j]!=s && val[j]==0) printf("%d %d\n", i, to[j]); return 0; } ``` ### [P2774 方格取数问题](https://www.luogu.com.cn/problem/P2774) #### 题意 $n\times m$ 个带权方格，取任意多个，不能取相邻两个，求获得的最大权值和。 #### 题解 我们可以考虑先取完所有方格，再不断的删去方格，直到合法为止。 显然，相邻的方格不能同时取，他们的横坐标和纵坐标有且仅有一个相差 $1$，它们的坐标和的奇偶性不同。 我们可以按照坐标和的奇偶性把所有方格分成 $2$ 部分，两个点连边代表他们不能同时取，即相邻。 这样就构成了一张二分图，我们把源点向左边的点连边，右边的点向汇点连边，边权为点权，左边和右边的点相邻就连边，边权为 $\inf$。 一个点如果取，代表源点可以到它或它可以到汇点，如果不去，这条边就不能选。 这样，如果源点到汇点联通，代表左边的点和右边的点一定同时取了，所以我们只要让图不连通，求最小割即可。 因为我们把中间的边权设成了 $\inf$，所以一定删掉，所以不会影响答案。 #### 代码 ```c++ int p(int x, int y) {return (x-1)*m+y;} int main() { n=read(), m=read(); s=n*m+1, t=n*m+2; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) { int x=read(); ans+=x; if ((i+j)&1) { if (i>1) add(p(i, j), p(i-1, j), 1e9), add(p(i-1, j), p(i, j), 0); if (i<n) add(p(i, j), p(i+1, j), 1e9), add(p(i+1, j), p(i, j), 0); if (j>1) add(p(i, j), p(i, j-1), 1e9), add(p(i, j-1), p(i, j), 0); if (j<m) add(p(i, j), p(i, j+1), 1e9), add(p(i, j+1), p(i, j), 0); add(s, p(i, j), x), add(p(i, j), s, 0); } else add(p(i, j), t, x), add(t, p(i, j), 0); } int flow; while (bfs()) while (flow=dinic(s, 1e9)) ans-=flow; printf("%d\n", ans); return 0; } ``` ### [P3355 骑士共存问题](https://www.luogu.com.cn/problem/P3355) #### 题意 在一个 $n\times n$ 的国际象棋棋盘中有些障碍，最多可以放几匹马，使得他们互不攻击 #### 题解 我们发现，和上面的一题十分像。 两个点不能同时取时，它们的坐标和的奇偶性不同。 连边方式不同，障碍物不连边，其他的和上面一样就好了！ #### 代码 ```c++ const int dx[8]={-2, -2, -1, -1, 1, 1, 2, 2}; const int dy[8]={-1, 1, -2, 2, -2, 2, -1, 1}; int p(int x, int y) {return (x-1)*n+y;} int main() { n=read(), m=read(), s=n*n+1, t=n*n+2; for (int i=1; i<=m; i++) { int x=read(), y=read(); f[x][y]=1; } for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { if (f[i][j]) continue; if ((i+j)&1) { for (int k=0; k<8; k++) { int x=i+dx[k], y=j+dy[k]; if (x<1 || x>n || y<1 || y>n || f[i][j]) continue; add(p(i, j), p(x, y), 1e9); add(p(x, y), p(i, j), 0); } add(s, p(i, j), 1), add(p(i, j), s, 0); } else add(p(i, j), t, 1), add(t, p(i, j), 0); } int maxflow=0, flow; while (bfs()) while (flow=dinic(s, 1e9)) maxflow+=flow; printf("%d\n", n*n-m-maxflow); return 0; } ``` #### [P2754 [CTSC1999]家园 / 星际转移问题](https://www.luogu.com.cn/problem/P2754) #### 题意 自己看题吧 #### 题解 数据范围特别小。 我们可以按时间分层，每个节点记录了天数和位置，再考虑连边。 首先每一天每个人可以在当前点不走，即从前一天的这个点到今天的这个点连一条边，边权无限。 对于每个路线，可以从前一天的这个点向今天到达的点连边，边权为飞船最大承载量，即最多这么多人可以走这条路。 当然，还要从超级源点向每一天的地球连边，每一天的月球向汇点连边。 枚举天数，在前一天的残量网络上跑网络流。 如果到达汇点的人数满足了，说明当前天可以到达。 如果很多天还不够，什么无解。 当然，无解也可以用并查集来判断，一个航道能到达的所有点显然可以互相到达，在同一个集合中，如果地球和月球不在同一个集合中，说明无解 #### 代码 ```c++ void ins(int x, int y, int z) {add(x, y, z); add(y, x, 0);} int main() { n=read()+2, m=read(), k=read(); for (int i=1; i<=m; i++) { h[i]=read(), r[i]=read(); for (int j=0; j<r[i]; j++) a[i][j]=read()+2; } while (day<500) { ins(s, day*n+2, 1e9); ins(day*n+1, t, 1e9); if (day) { for (int i=1; i<=n; i++) ins((day-1)*n+i, day*n+i, 1e9); for (int i=1; i<=m; i++) ins((day-1)*n+a[i][(day-1)%r[i]], day*n+a[i][day%r[i]], h[i]); } int flow=0; while (bfs()) while (flow=dinic(s, 1e9)) sum+=flow; if (sum>=k) break; day++; } printf("%d\n", day%500); return 0; } ``` ### 未完待续......（不会了，不想学网络流了qwq） 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏