题解

问题分析

题目要求选择不超过 ( K ) 条街道，最大化“覆盖路口的价值和”减去“所选街道的效应和”。核心挑战在于处理路口的重复覆盖（同一路口被多条街道覆盖时仅算一次价值），且需在大规模输入下高效求解。

核心思路

1. 随机化与网络流结合：

   • 利用随机化算法（如随机划分路口集合）生成候选方案，结合最大费用最大流模型评估方案价值。
   • 随机将路口划分为两个集合（通过 vis 数组标记），将街道转化为有向边，路口转化为节点，构建网络流模型。

2. 网络流建模：

   • 源点 ( S ) 连接未标记路口（vis[i]=0），边容量为 1 时费用为路口价值 ( p[i] )，超额容量费用为 0（确保路口价值仅算一次）。
   • 标记路口（vis[i]=1）连接汇点 ( T )，边容量为 1 时费用为路口价值 ( p[i] )，超额容量费用为 0。
   • 街道转化为有向边：若街道连接的两个路口分属不同集合，添加方向从非标记路口到标记路口的边，容量 1，费用为 -e_i（效应强度的负值）。

3. 最大费用流计算：

   • 使用 SPFA 算法求解最长路径（最大费用），通过增广路迭代计算最多 ( K ) 条街道的最大价值。
   • 多次随机划分路口集合，取所有方案的最大值作为答案。

代码解析

1. 随机化划分：

   • 每次迭代通过 rnd() 随机生成 vis 数组，将路口划分为两个集合，模拟不同的街道选择场景。

2. 网络流构建：

   • 根据 vis 数组划分，构建源点、汇点与路口、街道的连接边，将问题转化为最大费用流问题。
   • 街道边的方向和费用根据连接的路口是否属于同一集合动态调整。

3. SPFA 与增广路：

   • SPFA 算法用于寻找从源到汇的最长路径（最大费用），记录路径并进行流量增广。
   • 最多增广 ( K ) 次（对应选择 ( K ) 条街道），累加每次增广的费用得到当前方案的价值。

4. 结果优化：

   • 多次随机划分并计算，取最大值作为最终答案，通过随机性覆盖更多潜在最优解。

总结

该解法通过随机化划分路口集合，将问题转化为最大费用最大流模型，利用网络流算法求解每次划分的最优值，最终取多次结果的最大值。核心是通过随机化降低问题复杂度，结合网络流精准计算每次选择的价值，适用于题目约束下的大规模输入。时间复杂度依赖于随机迭代次数和网络流计算效率，通过参数调优可在实际数据中高效运行。