题目理解

我们有一个路由器网络，每条链路有距离（延迟），每个路由器有吞吐量限制（容量）。数据包必须沿着最短路径从 $1$ 到 $n$ 传输，要求计算最大吞吐量（即最大流，但只能在最短路径的边上流动）。

解题思路

这个问题可以拆成两个部分：

1.找出所有可能在最短路径上的边

用 Dijkstra 算法求出从路由器 $1$ 到所有点的最短距离 $dis[i]$。

一条边 $(u,v)$ 在最短路径上当且仅当 $dis[u] + w = dis[v]$。

2.在最短路径子图上求最大流

每个路由器有容量限制 $c[i]$，表示经过它的数据包数量不能超过 $c[i]$（起点 $1$ 和终点 $n$ 无限制）。

为了处理点容量，常用拆点技巧：将路由器 $i$ 拆成 $i$ 和 $i'$（代码中用 $i$ 和 $i+n$），中间连一条容量为 $c[i]$ 的边。

对于原图中的边 $(u,v)$，如果它在最短路径上，则在新图中连接 $u' \to v$（容量无穷大）。

最后在拆点后的图上，从 $1$ 到 $n'$（即 $n+n$）跑最大流。

算法步骤

1.读入 $n, m$ 和网络拓扑，用邻接矩阵存边（取最小重边）。

2.Dijkstra 求 $1$ 到各点的最短距离。

3.建最大流图：

每个点 $i$ 拆成 $i$（入点）和 $i+n$（出点）。

对于 $i=1$ 和 $i=n$，入点到出点容量为 $\infty$（起点终点无限制）。

对于 $2 \le i \le n-1$，入点到出点容量为 $c[i]$。

对于原边 $(u,v,w)$，如果 $dis[u] + w = dis[v]$，则从 $u+n$ 到 $v$ 连 $\infty$ 容量的边（双向都要判断）。

4.Dinic 算法 求 $1$ 到 $n+n$ 的最大流。

复杂度分析

$n \le 500$，$m \le 10^5$。

Dijkstra 用优先队列 $O((n+m)\log n)$。

Dinic 在拆点图上（$2n$ 个点，边数 $O(m)$）复杂度 $O((2n)^2 \cdot m)$ 在本题可接受。

代码关键点

用邻接矩阵 e[u][v] 存最小边权。

拆点技巧：$i$ 为入点，$i+n$ 为出点。

最短路径 DAG 建边时，要双向判断 dis[i] + e[i][j] == dis[j]。

Dinic 使用当前弧优化。

总结

本题结合了最短路和网络流两个知识点，通过拆点处理点容量，并在最短路径 DAG 上求最大流，是一道比较经典的图论综合题。