旅游安排 题解¶
解法署名：Johnson 重赋权与最小费用最大流建模来自出题人解法；Codex（GPT-6）采用逐次最短增广路实现费用流，并负责全图负环检测、边界处理及证明说明。
解法比较¶
出题人解法先求全图势函数，重赋权后逐起点做 Dijkstra，按距离与编号差选择目的地，再建立“出发人数—兴趣关系—接待容量”的最小费用最大流网络。势函数在路径上相消，整数流对应游客安排，这两项正确性依据与下文相同。出题人实现保存全部点对距离，使用队列松弛求势函数，费用流则沿零约化费用边推流，无法继续时调整可达点集与外界的费用差，使新边变成零费用，继续增广。
设兴趣边数为 \(q\) 、流网络边数为 \(e=O(n+q)\) .保存全部点对距离时，空间为 \(O(n^2+m+q)\) ；在有效势函数下，逐点 Dijkstra 为 \(O(n(m+n)\log(n+1))\) .标签调整费用流若做 \(a_0\) 次推流搜索、\(r\) 次标签调整，其工作量可按 \(O((a_0+r)(n+e))\) 计，复杂度必须包含这些次数。实现还须正确处理零个目标、全图负环和容量范围。
Codex 实现用 Bellman–Ford 的第 \(n\) 轮判据检测全图负环，逐起点用完距离即丢弃；费用流采用带势函数的 Dijkstra 逐次最短增广，单次按瓶颈容量推流。总空间降为 \(O(n+m+q)\) ，道路与增广时间的完整参数界见下文。优势是明确负环判据、免存距离矩阵与使用足够宽的数值类型；不同费用流实现未实测比较速度，仍保留实际增广次数参数。
检测全图负环并计算距离¶
负环即使处在没有游客的孤立区域，也必须报告。等价地添加一个到所有节点都有零长边的超级源点；实现时把所有势函数 \(h_i\) 初始化为零，对全部道路执行 Bellman–Ford 松弛。若第 \(n\) 轮仍能严格变小，则存在负环。
不存在负环时，每条边满足 \(h_v\le h_u+w(u,v)\) . 令
沿任意路径的势函数项都会相消，因此可在非负边权图上运行 Dijkstra，再还原
这使用 Johnson 的稀疏图最短路重赋权方法。每个有游客且 \(k_i>0\) 的起点单独计算距离，用完即可丢弃，不需要存完整距离矩阵。
目的地的精确选择¶
移除本村及不可达村子，对剩余村子按 \((d(i,j),\lvert i-j\rvert)\) 排序。取前 \(k_i\) 个，并纳入在截断处两项都相同的全部村子。
对于固定 \(i\) 和编号差，一个左侧编号与一个右侧编号至多各出现一次，所以任意排序键最多对应两个村子，入选数至多 \(k_i+1\) . 当 \(k_i=0\) 时直接取空集，不能访问排名 \(k_i-1\) . 游客数为零的起点可以跳过最短路与兴趣边，但仍须参与全图负环检查。
建立费用流网络¶
为每个村子建立出发节点 \(U_i\) 和接待节点 \(W_i\) ，另建源点 \(s\) 与汇点 \(t\) ：
- \(s\to U_i\) ：容量 \(V_i\) ，费用 \(0\) .
- \(U_i\to W_j\) ：仅当 \(j\) 为 \(i\) 的兴趣目的地时存在，容量可取 \(V_i\) ，费用为 \(C_iP_j\) .
- \(W_j\to t\) ：容量 \(H_j\) ，费用 \(0\) .
一单位流表示一名游客。整数容量保证能得到整数流，所有流量约束恰好对应居民数量与接待名额。每条源汇路径的费用等于这名游客的消费。因此，最小费用最大流就是所需答案。
未出游者不必在图中连一条“留在本村”的边。最大流已经决定尽可能多的人出游，其余人自然留在本村。
逐次最短增广¶
最初正向费用非负，流量为零，费用流势函数可以从零开始。每次在残量网络中按重赋权后的费用运行 Dijkstra，沿最短增广路一次推送整条路的瓶颈容量，再更新势函数。反向边的费用取负，使算法能够撤回此前的安排并改派游客。
一次增广保持“当前流量下费用最小”的性质：最短增广路具有最小新增费用，而残量网络中没有能改进当前流的负环。不断增广，直到不存在源汇路径；此时流量最大，且该流量下费用最小。不能因为下一条增广路费用为正就提前停止，题目先比较出游人数。
复杂度与数值范围¶
令兴趣关系数量为 \(q\) ，费用流网络边数为 \(e=O(n+q)\) ，令 \(a\) 为实际增广次数。道路阶段时间为 \(O(nm+n(m+n)\log(n+1)+n^2\log(n+1))\) ，其中最后一项是逐起点排序的上界；费用流阶段为 \(O(ae\log(n+1))\) . 总空间为 \(O(n+m+q)\) .
这里明确保留增广次数参数，不把大容量视为单位容量。每次按瓶颈容量批量增广；由于容量为整数，有通用上界 \(a\le F\le\sum_i V_i\) ，其中 \(F\) 是最大流量。这是逐次最短增广算法的伪多项式上界，不宣称强多项式保证。参考时限按所附最大规模测试实测。
最短路距离、容量、势函数和费用累计均使用 64 位有符号整数。最终费用不超过 \(900\sum_i V_i\) ，最多为 \(9\times10^{14}\) . 输入边权不能用消费价格替代，负道路长度只影响兴趣排名。
验证¶
独立小规模模型用 Floyd 计算距离，再按“每个具体游客前往哪一村或留在本村”枚举，按接待容量合并状态；依次比较出游人数和消费。含零兴趣、并列目的地、负边、负环、零消费和重复道路。性能测量见评测环境与性能。