「Nhk R2」Ustesiar - 题解

标签与难度

标签: 0-1分数规划, 二分答案, 二分图, 最大权完美匹配, KM算法, 图论, 最小费用最大流难度: 2400

题目大意喵~

主人你好呀，喵~ 这道题是这样的：我们有一张 $n$ 个点的有向图，每条边 $(u, v)$ 都有两个属性值 $a_i$ 和 $b_i$ 。我们的任务呢，是从图中选出一些边，组成一个或多个环，并且要满足一个非常严格的条件：图里的每一个点都必须恰好属于一个环，不多也不少哦！

在所有满足这个条件的选边方案中，我们要找到一种方案，使得所有选出的边（集合记为 $E$ ）的 $a$ 值总和，除以 $b$ 值总和，也就是这个比值 $\frac{\sum_{i \in E} a_i}{\sum_{i \in E} b_i}$ 达到最大！最后输出这个最大的比值就可以啦，喵~

举个例子，如果 $n=3$ ，一个合法的方案可以是边 $(1, 2), (2, 3), (3, 1)$ 组成一个大环。另一个合法的方案可以是自环（虽然题目说了无自环），比如 $(1,1), (2,3), (3,2)$ ，这样点 1 在一个环里，点 2 和 3 在另一个环里。

关键点在于“每个点恰好属于一个环”。这意味着，对于每个点 $u$ ，我们必须恰好选择一条从它出发的边 $(u, v)$ 。这就形成了一个每个点的出度都为 1 的图，这样的图结构正是一系列不相交的环的集合，也就是一个排列（Permutation）呢！

解题思路分析

这道题看起来有点吓人，又是环又是最大化分数的，但别怕，让我一步一步带你解开它的神秘面纱，喵~

第一步：分数规划的魔法喵~

一看到要最大化一个形如 $\frac{\sum a_i}{\sum b_i}$ 的式子，我们聪明的直觉就应该告诉我们，这很可能是一个 0-1 分数规划 问题！

假设我们要求的最大比值是 $\lambda$ 。那么，对于一个合法的选边方案 $E$ ，一定满足：

\frac{\sum_{i \in E} a_i}{\sum_{i \in E} b_i} \le \lambda

我们来对这个式子做一点小小的变形。假设 $\sum_{i \in E} b_i > 0$ （题目通常会保证这一点），我们可以把分母乘到右边去：

\sum_{i \in E} a_i \le \lambda \sum_{i \in E} b_i

再把所有项移到一边：

\sum_{i \in E} a_i - \lambda \sum_{i \in E} b_i \le 0

\sum_{i \in E} (a_i - \lambda \cdot b_i) \le 0

这个式子告诉我们一个非常重要的信息！对于任何合法的选边方案 $E$ ，它对应的 $\sum (a_i - \lambda \cdot b_i)$ 的值都小于等于 0。这意味着，如果我们取所有合法方案中，能让这个和式取到最大值的那个方案，它的值也一定小于等于 0。

也就是说，如果我们定义一个函数 $g(\lambda) = \max_{E} \left\{ \sum_{i \in E} (a_i - \lambda \cdot b_i) \right\}$ ，那么当 $\lambda$ 是我们要求的最大比值时，一定有 $g(\lambda) = 0$ 。

第二步：二分答案大法好！

$g(\lambda)$ 这个函数有一个很棒的性质，那就是它是单调递减的。为什么呢？因为 $\lambda$ 前面的系数是 $-\sum b_i$ ，而 $b_i$ 通常是正数，所以 $\lambda$ 越大， $a_i - \lambda \cdot b_i$ 就越小，它们的和的最大值自然也越小啦。

对于单调的函数，我们就可以愉快地使用 二分答案 了！我们可以二分猜测最终的答案 $\lambda$ 。

对于一个我们猜的 mid 值：

我们计算出所有边的“新权值” $w_i = a_i - \text{mid} \cdot b_i$ 。
然后我们去解决一个新的问题：在所有合法的选边方案中，找到一个方案 $E$ ，使得 $\sum_{i \in E} w_i$ 最大。
得到这个最大的和之后，我们检查一下：
- 如果这个最大和 $\ge 0$ ，说明我们有可能找到一个方案，使得 $\frac{\sum a_i}{\sum b_i} \ge \text{mid}$ 。这意味着真正的答案 $\lambda$ 可能比 mid 更大（或者就是mid），所以我们应该在 [mid, r] 的范围里继续寻找，即 l = mid。
- 如果这个最大和 $< 0$ ，说明对于任何方案， $\sum(a_i - \text{mid} \cdot b_i)$ 都是负的，即 $\frac{\sum a_i}{\sum b_i} < \text{mid}$ 。这说明我们猜的 mid 太大了，真正的答案 $\lambda$ 一定在 mid 的左边，所以我们应该在 [l, mid] 的范围里继续寻找，即 r = mid。

这样不断二分，我们就能把 $\lambda$ 的范围缩得很小，直到满足精度要求为止，喵~

第三步：子问题的华丽变身——最大权完美匹配！

现在，核心问题就变成了：对于一个固定的 mid，如何找到一个合法的选边方案，使得新权值之和 $\sum (a_i - \text{mid} \cdot b_i)$ 最大？

我们再回顾一下“合法的选边方案”是什么：每个点都恰好有一个出边。这不就是让我们为每个点 $u \in \{1, \dots, n\}$ 找一个配对的点 $v \in \{1, \dots, n\}$ ，选择边 $(u,v)$ 吗？

这正是 二分图的最大权完美匹配 问题！我们可以把原图改造成一个二分图：

建立一个有 $n$ 个点的左部（U部），代表边的起点。
建立一个有 $n$ 个点的右部（V部），代表边的终点。
对于原图中的每一条边 $(u, v)$ ，我们在二分图中连一条从左部的 $u$ 到右部的 $v$ 的边，其权重就是我们刚刚计算的 $w_{uv} = a_{uv} - \text{mid} \cdot b_{uv}$ 。

现在，我们要找一个 完美匹配（即每个左部点都恰好匹配一个右部点），并且这个匹配的总权重最大。

解决最大权完美匹配，我们有经典的 KM (Kuhn-Munkres) 算法！

第四步：闪亮登场！KM算法喵~

KM算法是一种非常优雅的算法，专门用来解决二分图最大权完美匹配问题。它的核心思想是利用 顶标 (vertex label)。

顶标和相等子图:
- 我们给左部的每个点 $x$ 一个顶标 $l_x$ ，给右部的每个点 $y$ 一个顶标 $r_y$ 。
- 在任何时候，这些顶标都必须满足一个条件：对于图中的任意一条边 $(x, y)$ ，都有 $l_x + r_y \ge w_{xy}$ 。
- 所有满足 $l_x + r_y = w_{xy}$ 的边组成的子图，我们称之为 相等子图。
- KM算法的精髓就在于：如果在相等子图中能找到一个完美匹配，那么这个匹配就是原图的最大权完美匹配！ 为什么呢？因为这个匹配的总权值为 $\sum w_{xy} = \sum (l_x + r_y) = \sum l_x + \sum r_y$ 。而对于任何一个完美匹配，其总权值 $\sum w'_{xy} \le \sum (l_x + r_y)$ 。所以相等子图里的完美匹配一定是权值最大的！
算法流程:
- 初始化:
  - 给右部顶标 $r_y$ 全部初始化为 0。
  - 给左部顶标 $l_x$ 初始化为与它相连的边的最大权重，即 $l_x = \max_{y} \{w_{xy}\}$ 。这样就保证了初始时 $l_x + r_y \ge w_{xy}$ 。
- 为每个左部点寻找匹配:
  - 我们依次尝试为左部的每个点 $x$ 寻找一个匹配对象。
  - 我们从 $x$ 出发，在当前的相等子图中，通过DFS或BFS寻找增广路。
  - 如果找到了增广路，太棒了！我们更新匹配关系，然后处理下一个左部点。
  - 如果找不到增广路，说明当前的相等子图还不够“大”，我们需要修改顶标来把更多的边加入到相等子图中。
- 修改顶标:
  - 在寻找增广路的过程中，我们会访问到一些左部点（设为集合 $S$ ）和一些右部点（设为集合 $T$ ）。
  - 我们计算一个差值 $\Delta = \min_{x \in S, y \notin T} \{l_x + r_y - w_{xy}\}$ 。这个 $\Delta$ 是所有“一个端点在增广路径上，另一个不在”的边中最接近进入相等子图的那个。
  - 然后我们更新顶标：所有 $x \in S$ 的点， $l_x \leftarrow l_x - \Delta$ ；所有 $y \in T$ 的点， $r_y \leftarrow r_y + \Delta$ 。
  - 这样修改后，至少会有一条新的边 $(x, y)$ 满足 $l_x + r_y = w_{xy}$ ，从而加入了相等子图。然后我们就可以继续为点 $x$ 寻找增广路了。
- 结束: 当所有左部点都成功匹配，我们就找到了最大权完美匹配，它的权值就是 $\sum l_x + \sum r_y$ （或者直接加匹配边的权值）。

把这一切组合起来，我们就得到了完整的解法：二分答案 $\lambda$ ，在 check 函数里用 KM 算法计算最大权完美匹配的权值，然后根据权值与0的关系来调整二分区间。完美，喵~

代码实现

下面是我根据这个思路，精心重构的一份代码，加了好多注释，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const double INF_WEIGHT = 1e18; // 使用一个很大的数表示无穷大
const double EPS = 1e-7;       // 二分答案的精度

int n; // 节点数量
int m; // 边的数量

// 存储原始边的信息
struct Edge {
    int u, v, a, b;
};
vector<Edge> edges;

// KM算法所需的变量
int match_y[105];         // match_y[j] 存储右部点 j 匹配的左部点
double label_l[105];      // 左部点的顶标
double label_r[105];      // 右部点的顶标
bool visited_x[105];      // DFS时记录左部点是否访问过
bool visited_y[105];      // DFS时记录右部点是否访问过
double slack[105];        // slack[j] 存 min(label_l[i] + label_r[j] - w[i][j])
double weight_matrix[105][105]; // 权重矩阵

// KM算法的DFS部分，为左部点u寻找匹配
bool dfs_match(int u) {
    visited_x[u] = true;
    for (int v = 1; v <= n; ++v) {
        if (visited_y[v]) continue;

        double gap = label_l[u] + label_r[v] - weight_matrix[u][v];
        if (abs(gap) < EPS) { // 如果边(u,v)在相等子图中
            visited_y[v] = true;
            // 如果v未被匹配，或者v的匹配对象可以找到新的匹配
            if (match_y[v] == 0 || dfs_match(match_y[v])) {
                match_y[v] = u;
                return true;
            }
        } else {
            // 更新slack值，为后续修改顶标做准备
            slack[v] = min(slack[v], gap);
        }
    }
    return false;
}

// KM算法主过程
double km_solve() {
    // 初始化顶标
    fill(label_r + 1, label_r + n + 1, 0.0);
    for (int i = 1; i <= n; ++i) {
        label_l[i] = -INF_WEIGHT;
        for (int j = 1; j <= n; ++j) {
            label_l[i] = max(label_l[i], weight_matrix[i][j]);
        }
    }

    fill(match_y + 1, match_y + n + 1, 0);

    // 为每个左部点寻找匹配
    for (int i = 1; i <= n; ++i) {
        while (true) {
            fill(visited_x + 1, visited_x + n + 1, false);
            fill(visited_y + 1, visited_y + n + 1, false);
            fill(slack + 1, slack + n + 1, INF_WEIGHT);
            
            if (dfs_match(i)) {
                break; // 成功找到匹配，处理下一个左部点
            }

            // 未找到匹配，需要修改顶标
            double delta = INF_WEIGHT;
            for (int j = 1; j <= n; ++j) {
                if (!visited_y[j]) {
                    delta = min(delta, slack[j]);
                }
            }
            
            // 如果delta无穷大，说明图不连通，可能无完美匹配（本题保证有解）
            if (delta > INF_WEIGHT / 2) break;

            for (int j = 1; j <= n; ++j) {
                if (visited_x[j]) label_l[j] -= delta;
                if (visited_y[j]) label_r[j] += delta;
            }
        }
    }

    // 计算最大权匹配的总权重
    double max_weight_sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (match_y[i] != 0) {
            max_weight_sum += weight_matrix[match_y[i]][i];
        }
    }
    return max_weight_sum;
}

// 二分答案的check函数
bool check(double ratio_guess) {
    // 1. 构建权重矩阵 w[i][j] = a_ij - ratio_guess * b_ij
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            weight_matrix[i][j] = -INF_WEIGHT;
        }
    }
    for (const auto& edge : edges) {
        weight_matrix[edge.u][edge.v] = edge.a - ratio_guess * edge.b;
    }
    
    // 2. 运行KM算法计算最大权完美匹配
    double max_weight = km_solve();
    
    // 3. 判断最大权是否>=0
    return max_weight >= 0;
}


int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    edges.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].a >> edges[i].b;
    }
    
    // 二分答案
    double l = 0.0, r = 2000.0; // 根据a和b的范围设定一个足够大的上界
    // 迭代固定次数（如100次）通常比用eps更稳定
    for(int iter = 0; iter < 100; ++iter) {
        double mid = l + (r - l) / 2;
        if (check(mid)) {
            l = mid; // mid可行，尝试更大的答案
        } else {
            r = mid; // mid不可行，答案在左侧
        }
    }

    cout << fixed << setprecision(10) << l << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(\text{iterations} \cdot N^3)$
- 外层是二分答案，我们迭代一个固定的次数，比如 100 次，可以看作是常数 $\text{iterations}$ 。
- 内层的 check 函数主要是 KM 算法的开销。一个朴素的 KM 算法实现，对于每个左部点，最坏情况下可能需要多次修改顶标才能找到匹配。每次修改顶标需要 $O(N^2)$ 的时间来遍历所有边更新 slack 值和顶标，而一个左部点最多需要进行 $N$ 次成功的匹配尝试。所以总的复杂度是 $O(N \cdot N \cdot N) = O(N^3)$ 。
- 因此，总时间复杂度就是 $O(\text{iterations} \cdot N^3)$ ，其中 $N$ 是点的数量。
空间复杂度: $O(N^2)$
- 主要的开销来自于存储二分图的权重矩阵 weight_matrix[N][N]，这需要 $O(N^2)$ 的空间。
- 其他的辅助数组如 match_y, label_l, label_r, visited_x, visited_y, slack 等都是 $O(N)$ 的，所以总空间复杂度由权重矩阵决定，为 $O(N^2)$ 。

知识点总结

这真是一道融合了多种算法思想的超棒题目，喵~ 解完它感觉自己的小爪子都变厉害了呢！

0-1 分数规划: 这是解决一类最优化比值问题的标准模型。关键在于将 $\max \frac{\sum a_i}{\sum b_i}$ 转化为判定性问题 $\max \sum(a_i - \lambda \cdot b_i) \ge 0$ 是否成立。
二分答案: 分数规划问题天然地与二分答案相结合。通过二分枚举比值 $\lambda$ ，将最优化问题转化为判定性问题。对于浮点数的二分，迭代固定次数是一种常见且稳定的做法。
二分图最大权完美匹配: 问题的核心子任务。理解如何将原图问题（寻找覆盖所有点的圈）转化为二分图上的匹配问题是关键一步。
KM (Kuhn-Munkres) 算法: 解决二分图最大权完美匹配的经典高效算法。理解其顶标、相等子图、修改顶标以扩大相等子图的核心思想，是掌握该算法的重点。

希望我的这篇题解能帮助到你哦！如果还有不明白的地方，随时可以再来问我，喵~ 加油！

「Nhk R2」Ustesiar - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：分数规划的魔法喵~ ​

第二步：二分答案大法好！ ​

第三步：子问题的华丽变身——最大权完美匹配！ ​

第四步：闪亮登场！KM算法喵~ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​