[蓝桥杯]小凯的疑惑

小凯的疑惑题目描述小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。输入描述输入数据仅一行，包含两个正整数 aa 和 bb，它们之间用一个空格隔开，表示小凯手中金币的面值。其中，1≤a，b≤1091≤

鑫鑫向栄

567人浏览 · 2025-06-08 10:45:04

鑫鑫向栄 · 2025-06-08 10:45:04 发布

小凯的疑惑

题目描述

小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？注意：输入数据保证存在小凯无法准确支付的商品。

输入描述

输入数据仅一行，包含两个正整数 aa 和 bb，它们之间用一个空格隔开，表示小凯手中金币的面值。

其中，1≤a，b≤1091≤a，b≤109。

输出描述

输出仅一行，一个正整数 NN，表示不找零的情况下，小凯用手中的金币不能准确支付的最贵的物品的价值。

输入输出样例

示例

输入

3 7

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 644 | 总提交次数: 680 | 通过率: 94.7%

难度: 困难标签: 2017, 构造, NOIP

算法思路

本题是最小路径覆盖问题的变种，核心思想是通过有向无环图（DAG）建模，并利用二分图匹配求解。具体思路如下：

问题转换：
- 将每个标记为 1 的格子视为图中的一个节点。
- 若从格子 A 可以向右或向下走到格子 B（即 B 在 A 的右侧或下方且相邻），则建立一条从 A 到 B 的有向边。
- 目标：用最少的路径覆盖所有节点（路径可重叠），且每条路径必须沿有向边移动。
最小路径覆盖模型：
- 对于可重叠路径覆盖，需先求图的 传递闭包（即若 A 能间接到达 C，则添加边 A→C）。
- 最小路径覆盖数 = 节点总数 - 二分图最大匹配数。
- 二分图建模：
  - 将每个节点拆分为两个点：左部（起点）和右部（终点）。
  - 对传递闭包中的每条边 (u, v)，从左部 u 向右部 v 连边。
匈牙利算法：
求二分图的最大匹配，匹配数越大，路径数越少。

图片演示

以下用 2×2 矩阵 (11/11) 演示传递闭包和匹配过程：

初始矩阵      节点编号     传递闭包      二分图匹配
1 1         (1) (2)     1→2, 1→3    左部[1,2] 
1 1         (3) (4)     1→4, 2→4    右部[1,2,3,4]
            2→3, 2→4
            3→4

最大匹配：
左部1→右部2、左部2→右部4 → 匹配数=2
最小路径覆盖：4 节点 - 2 匹配 = 2 条路径（如 (1)→(2)→(4) 和 (3)）

算法步骤

节点编号：遍历矩阵，为每个 '1' 分配唯一编号。
构建传递闭包：
- 用 BFS/DFS 或动态规划，计算每个节点可达的所有节点。
- 例：若 A 可达 B 和 C，且 B 可达 C，则闭包包含 A→B、A→C、B→C。
二分图建边：对闭包中每条边 (u, v)，从左部 u 向右部 v 连边。
匈牙利算法：
- 初始化 match 数组记录匹配关系。
- 对每个左部节点，DFS 寻找增广路径。
计算结果：
最小路径数 = 节点总数 - 最大匹配数。

C++代码实现

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 405; // 最大节点数 (200 * 2)
vector<int> graph[MAXN]; // 传递闭包的邻接表
bool closure[MAXN][MAXN]; // 传递闭包矩阵
int id[25][25]; // 节点编号
int match[MAXN]; // 右部匹配的左部节点
bool vis[MAXN]; // DFS访问标记
int n, m, tot = 0;
char grid[25][25];

// 从节点u出发求传递闭包 (BFS)
void bfs(int start, vector<int>& reachable) {
    queue<int> q;
    q.push(start);
    vector<bool> visited(MAXN, false);
    visited[start] = true;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                reachable.push_back(v);
                q.push(v);
            }
        }
    }
}

// 匈牙利算法：为左部节点u找匹配
bool dfs(int u) {
    for (int v : graph[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> grid[i];

    // 步骤1：给 '1' 的格子分配编号
    memset(id, -1, sizeof(id));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                id[i][j] = tot++;
            }
        }
    }

    // 步骤2：构建初始图 (一步可达的边)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '1') continue;
            int u = id[i][j];
            // 向右走
            if (j + 1 < m && grid[i][j + 1] == '1') {
                int v = id[i][j + 1];
                graph[u].push_back(v);
            }
            // 向下走
            if (i + 1 < n && grid[i + 1][j] == '1') {
                int v = id[i + 1][j];
                graph[u].push_back(v);
            }
        }
    }

    // 步骤3：计算传递闭包
    memset(closure, false, sizeof(closure));
    for (int i = 0; i < tot; i++) {
        vector<int> reachable;
        bfs(i, reachable); // 从i出发的可达节点
        for (int v : reachable) {
            closure[i][v] = true;
        }
    }

    // 重建邻接表：基于传递闭包
    for (int i = 0; i < MAXN; i++) graph[i].clear();
    for (int i = 0; i < tot; i++) {
        for (int j = 0; j < tot; j++) {
            if (closure[i][j]) {
                graph[i].push_back(j); // 左部i → 右部j
            }
        }
    }

    // 步骤4：匈牙利算法求最大匹配
    memset(match, -1, sizeof(match));
    int max_match = 0;
    for (int i = 0; i < tot; i++) {
        memset(vis, false, sizeof(vis));
        if (dfs(i)) max_match++;
    }

    // 步骤5：最小路径覆盖 = 总节点数 - 最大匹配数
    cout << tot - max_match << endl;
    return 0;
}

代码解析

节点编号：
- 遍历矩阵，为每个 '1' 分配唯一 id（从 0 开始）。
初始图构建：
- 对每个 '1'，检查其 右侧 和 下方 相邻格子，若为 '1' 则建边。
传递闭包计算：
- 使用 BFS 计算每个节点可达的所有节点，记录在 closure 矩阵中。
二分图重建：
- 基于传递闭包，从左部节点向所有可达的右部节点建边。
匈牙利算法：
- match[v] = u 表示右部节点 v 匹配到左部节点 u。
- DFS 递归搜索增广路径，更新匹配关系。
结果计算：
- tot - max_match 即最小路径覆盖数。

实例验证

输入：

步骤分析：

节点编号：共 13 个 '1'（tot=13）。
传递闭包：
- 节点 (0,2) 可达 (1,2), (1,3), (1,4), (2,2), (3,2), (4,2) 等。
最大匹配：
- 闭包图的最大匹配数为 10（如 (0,2)→(1,2), (1,0)→(1,1), (3,0)→(3,1) 等）。
结果计算：
- 最小路径数 = 13 - 10 = 3（输出 3）。

三条路径示例：

(1,0) → (1,1) → (1,2) → (1,3) → (1,4)
(3,0) → (3,1) → (3,2) → (3,3) → (3,4)
(0,2) → (1,2) → (2,2) → (3,2) → (4,2)

注意事项

传递闭包的必要性：
- 直接使用一步可达边会忽略间接可达关系，导致匹配不足（如实例中匹配数从 8 提升到 10）。
节点编号唯一性：
- 每个 '1' 必须有唯一 id，且需跳过 '0' 格子。
匈牙利算法优化：
- 使用 vis 数组避免重复访问，每次 DFS 前重置。
边界条件：
- 当矩阵全 0 时，路径数为 0（题目保证存在 '1'）。

测试点设计

测试点	矩阵规模	1 的数量	特点	预期结果
1	1×1	1	单点	1
2	2×2	4	全 1	2
3	3×3	5	十字交叉	2
4	5×5	13	题目示例	3
5	20×20	200	最大规模	80~100

优化建议

传递闭包优化：

改用 动态规划 计算闭包（因方向固定：只能向右/向下）：

for (int k = 0; k < tot; k++)
    for (int i = 0; i < tot; i++)
        for (int j = 0; j < tot; j++)
            closure[i][j] |= (closure[i][k] && closure[k][j]);