P3403 跳楼机 题解（同余最短路）

· · 题解

同余最短路在 OI Wiki 上的例题。

同余最短路的题目，在题面上看起来更类似于数学题，而不是图论题。

它可以解决以下问题：

  1. 给定 n 个整数，求这 n 个整数能拼凑出多少的其他整数（n 个整数可以重复取）；
  2. 以及「给定 n 个整数，求这 n 个整数不能拼凑出的最小（最大）的整数」；
  3. 或者「至少要拼几次才能拼出模 K 余 p 的数」的问题。

首先可以发现，4 个操作中，第 4 个操作是没有任何作用的，实际上只有前 3 种操作有用。

则本题的题意就是给定 3 个整数，3 个整数可以重复取，求在 [1, h] 的范围内，可以拼出多少其他整数

设输入为 x, y, z，则该问题可以看作以下问题：

给定 x, y, z，a, b, c 为非负整数，要求 a,b,c 三个未知量的式子 ax + by + cz 的值在 [1,h] 范围内，求该式子有多少种可能的结果。

首先，我们可以把 [1,h] 的所有整数进行分类。

我们把 [1,h] 的数，按照 x 的同余类进行分类，则在同一个同余类中的数，总能通过不断地 +x 凑得。

此时，我们只要求出每个同余类中，能够凑得的最小的数字，这样在该同余类中更大的数字也一定都能凑得。

比如说，x 为 5，则对于同余类 [2]，假设该同余类中最小能凑得的数是 7，则通过不断 +x，在同一个同余类中的 12, 17, 22... 都是能凑得的。

假设可以求出，每一个同余类 [i] 中，可以凑出的最小数字为 d[i]，则该同余类内总共有 \lfloor \frac{h - d[i]}{x} \rfloor + 1 个数字时可以凑出的。

该式子可以这么理解：首先 d[i] 可以凑出，所以后面有一个 +1。

而对于剩余的数，每增加 x 都能再找到该同余类中的下一个数，因此，一直增加到 h，总共能找到 \lfloor \frac{h - d[i]}{x} \rfloor 个数。

当然，如果 d[i] \gt h，该同余类对答案的贡献就为 0，不累加到答案中。

接下来，只要知道如何求出 d[i] 即可。

构建同余最短路的图论模型前，首先可以先明确起点。

对于本题，当不进行任何操作的时候，一开始我们就在第一层，因此对于 x 的同余类 [1]，显然能得知该同余类内最小能凑得的数为 1，则 d[1] = 1。

（然而这里稍微有一点坑，可以看后面的解释）

之后再考虑如何图论建模。

现在我们把整段值域按照 x 的同余类进行了分类，而要求出每个同余类内能凑出的最小数，实际上增减 x 这个值是没有任何作用的。

因为无论如何 +x，我们也只是一直在同一个同余类内找之后的数字，不会转换到其他同余类内。

因此，我们利用 x 得到了 0 至 x-1 这 x 个结点，而对于边，我们需要使用 y,z 两个值来进行连边。

连边的方法是，对于每一个结点 i，都向结点 (i + y) \bmod x 连一条边权为 y 的边。

对于每一个结点 i，都向结点 (i + z) \bmod x 连一条边权为 z 的边。

边的意义是，假设当前有一个在同余类 [i]（结点 i） 内的数字，通过 +y，我们会获得一个在同余类 [(i + y) \bmod x] 内的数字（后继结点）。

并且，与原本的数字相比，转到另一个同余类后，数字的大小变大了 y（边权）。

照这样子建完所有的边，就可以从刚才说的起点 1 号结点跑一遍单源最短路，这样就相当于，从起点开始通过 +y 和 +z 开始凑数，凑出 x 的每个同余类内的数字。

到达每个结点的路径，就是凑出一个位于该同余类内的数字的一种方法，这段路径的边权和就是凑出的这个数字。

而凑出的最小的数字，刚好就是最短路径的距离，即 d[i]。

算出 d[i] 之后，按照上面的式子统计答案即可。

设置起点时存在一个坑，如果弄错了就会 WA 在第一个测试点，得到 90 分。

设置起点时，我们会很自然地认为应该设置 d[1] = 1，但是考虑一下，如果 x = 1，是否还存在同余类 [1]？

显然是不存在的，因此设置起点时应该设置 d[1 \bmod x] = 1，这样才能保证正确。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll n;           // 链式前向星表头习惯用 h，因此输入的 h 就用 n 来命名
int x, y, z;

// 点数：点数就是 x 的同余类的个数，x 最大为 N，则点需要 N 个
// 边数：每个点都需要往后利用 y 连一条边，再利用 z 连一条边，因此总共有 2*N 条边
int h[N], e[N << 1], nxt[N << 1], idx;
ll w[N << 1];

// dij 用到的数据结构
ll d[N];
bool vis[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;

ll ans;

// 添加一条从 f 指向 t，边权为 v 的边
void add(int f, int t, ll v)
{
    e[idx] = t;
    w[idx] = v;
    nxt[idx] = h[f];
    h[f] = idx;
    idx++;
}

void dij(int s)
{
    memset(d, 0x7f, sizeof(d)); // 初始化整个数组为无穷大

    #if 0   // 按照这个方式设置起点是错的，上面说过了
    d[s] = 1;
    q.push({1, s});
    #endif

    d[s % x] = 1;           // 正确的起点设置方法
    q.push({1, s % x});

    // 以下都是模板
    pair<ll, int> t;
    int sec, u;
    ll fir, v;

    while (!q.empty())
    {
        t = q.top();
        q.pop();
        fir = t.first;
        sec = t.second;

        if (vis[sec]) continue;
        vis[sec] = true;

        for (int i = h[sec]; ~i; i = nxt[i])
        {
            u = e[i];
            v = w[i];

            if (d[u] > d[sec] + v)
            {
                d[u] = d[sec] + v;
                q.push({d[u], u});
            }
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(h, -1, sizeof(h));   // 初始化链式前向星表头

    cin >> n;
    cin >> x >> y >> z;

    for (int i = 0; i < x; i++)     // 对于每个同余类，往后连边
    {
        add(i, (i + y) % x, y);     // 按照推导，利用 y、z 往后连边
        add(i, (i + z) % x, z);
    }

    dij(1); // 从起点 1 跑单源最短路

    for (int i = 0; i < x; i++)
    {
        if (d[i] <= n)  // 注意条件
        {
            ans += (n - d[i]) / x + 1;  // 统计答案
        }
    }

    cout << ans;

    return 0;
}