题目分析

本题描述了一个有向无环图的交通网络，我们需要通过调整道路容量来优化总费用，目标是最大化调整后的费用节省与调整次数的比率 $(X - Y)/k$。

关键洞察

1. 问题本质

这是一个最优比率问题，属于分数规划的范畴。我们需要找到最大的比值 $r = (X - Y)/k$。

2. 图论建模

将交通网络转化为图论问题：

• 节点：交通节点
• 边：道路，带有多种费用参数
• 调整操作：对应图中边的权重变化

3. 差分约束思想

通过建立不等式关系，将容量调整的约束条件转化为图的边权约束。

算法思路

分数规划 + SPFA 正环检测

核心公式转化

设最优比率为 $r$，则有：

转化为：

图构建策略

对于每条可调整的道路 $(u, v, a, b, c, d)$：

1. 扩容操作（容量 +1）：

   • 费用变化：运输费用增加 $d$，调整费用 $b$
   • 总费用变化：$b + d$
   • 建边：$u \to v$，权值 $b + d$

2. 压缩操作（容量 -1）：

   • 费用变化：运输费用减少 $d$，调整费用 $a$
   • 总费用变化：$a - d$
   • 建边：$v \to u$，权值 $a - d$（仅当 $c > 0$ 时可压缩）

环检测原理

在分数规划的二分解法中，对于候选比率 $mid$：

• 将每条边的权值减去 $mid$
• 如果图中存在正环，说明当前比率 $mid$ 可达
• 通过 SPFA 算法检测正环

代码实现详解

#include <bits/stdc++.h>
using namespace std;
#define il inline

const int N = 5e3 + 5, M = 3e3 + 5;
const double eps = 1e-3;

int n, m, st, cnt = 1;
int head[N], tot[N];
double dis[N];
bool inq[N];
struct Edge {
    int v, w, to;
} e[M << 1];

il void AddEdge(int u, int v, int w) {
    e[cnt] = {v, w, head[u]};
    head[u] = cnt++;
    return ;
}

il bool SPFA(double mid) {
    for (int i = 1; i <= n + 2; i++)
        dis[i] = 1e7, inq[i] = false;

    queue<int>q;
    dis[st] = tot[st] = 0, inq[st] = true, q.push(st);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;

        for (int i = head[u]; i; i = e[i].to) {
            int v = e[i].v, w = e[i].w;

            if (dis[u] + w + mid < dis[v]) {
                dis[v] = dis[u] + w + mid, tot[v] = tot[u] + 1;

                if (tot[v] > n)
                    return true;

                if (!inq[v])
                    inq[v] = true, q.push(v);
            }
        }
    }

    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, a, b, c, d;
        cin >> u >> v >> a >> b >> c >> d;

        if (u != n + 1) {
            if (c)
                AddEdge(v, u, a - d);

            AddEdge(u, v, b + d);
        } else
            st = v;
    }

    double l = 0, r = 1e3, ans = 0;

    while (r - l > eps) {
        double mid = (l + r) / 2;

        if (SPFA(mid))
            ans = mid, l = mid + eps;
        else
            r = mid - eps;
    }

    cout << fixed << setprecision(2) << ans;
    return 0;
}

算法步骤

1. 输入处理：读取网络结构和参数
2. 图构建：
   • 为每条可调整道路建立扩容边和压缩边
   • 排除与起点直接相连的不可调整道路
3. 二分搜索：在 $[0, 1000]$ 范围内搜索最优比率
4. 环检测：对每个候选比率，使用 SPFA 检测正环
5. 结果输出：输出找到的最大比率

复杂度分析

• 时间复杂度：$O(kM \log C)$，其中 $k$ 是 SPFA 常数，$M$ 是边数，$C$ 是二分范围
• 空间复杂度：$O(N + M)$

关键点说明

1. 为什么检测正环？

   • 正环对应着一个费用节省的循环调整方案
   • 沿着正环无限循环调整，可以使 $(X - Y) - r \cdot k$ 无限增大

2. 起点处理：

   • 与起点直接相连的道路不可调整
   • 从起点连接的下一节点开始搜索

3. 精度控制：

   • 使用 $eps = 10^{-3}$ 保证精度要求
   • 二分范围 $[0, 1000]$ 覆盖了所有可能的费用比率