
## 并查集

并查集是一种用于管理元素所属集合的数据结构，

并查集支持两种操作：

- 合并（`merge`）：合并两个节点所属的结合（合并两个树）
- 查询（`find`）：查询某个节点所对应的集合

使用路径压缩后的并查集的平均时间复杂度为 $O(\alpha(n))$ ，其中 $\alpha(n)$ 表示阿克曼函数的反函数。在宇宙可观测的 $n$ 中，$\alpha(n) \leq 5$ ，即路径压缩后的平均时间复杂度为渐进 $O(1)$ 。但是，可以构造特殊数据使得朴素路径压缩（没有进行按秩合并）的并查集实现达到单次查询 $O(\log n)$ 的最坏时间复杂度。具体证明和验证见 <https://leetcode.cn/problems/number-of-provinces/solutions/550060/jie-zhe-ge-wen-ti-ke-pu-yi-xia-bing-cha-0unne/> 以及 <https://oi-wiki.org/ds/dsu-complexity/#%E4%B8%BA%E4%BD%95%E5%B9%B6%E6%9F%A5%E9%9B%86%E4%BC%9A%E8%A2%AB%E5%8D%A1> 。一般情况下可以认为并查集实现为均摊 $O(1)$ 。

若追求严格 $O(1)$ ，可以通过按秩合并或启发式合并实现最坏 $O(\alpha(n))$ 即均摊 $O(1)$ 的时间复杂度。详见 <https://oi-wiki.org/ds/dsu/#%E5%90%88%E5%B9%B6> 。

本文将仅采用路径压缩的朴素并查集。下面给出面向对象的模板代码：

```cpp
class DSU {
private:
    int fa[N];

public:
    DSU() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};
```

注意 `fa[i]` 数组的初始化赋值。

## 例题

### [P2024 [NOI2001] 食物链](https://www.luogu.com.cn/problem/P2024)

#### 题目大意

有 A 吃 B 、B 吃 C 、C 吃 A 三种狩猎关系，保证给出的每个动物都是 A, B, C 中的一种，判断对于每条给定信息是否与先前信息矛盾。输出矛盾信息的总数。

每条信息分为两类：

1. 给定 X 和 Y ，表示 X 和 Y 是同类；
2. 给定 X 和 Y ，表示 X 吃 Y 。

#### 题目分析

显然可以通过种类并查集暴力维护，具体实现方法不在此赘述。此处将主要探讨带权并查集的解法。

不妨对 X, Y 可能产生的所有关系进行枚举。规定如下权值：

- `0` 表示此节点与父节点为同类；
- `1` 表示此节点被父节点吃；
- `2` 表示此节点吃父节点。

随后对每个可能的合法关系进行枚举，得到下表：

| 节点 X 与父关系 | 节点 X 与 Y 关系 |  节点 Y 与父关系|
| :----------: | :----------: | :----------: |
|0  |  0|  0|
|0  | 1 |  1|
|  0| 2 |  2|
|  1|  0|  1|
|  1|  1|  2|
|  1|  2|  0|
|  2|  0|  2|
|  2|  1|  0|
|  2|  2|  1|

设 $w_i$ 表示节点 $i$ 与其父节点的关系。观察规律可得，有 $w_Y = (w_{X,Y}' + w_X) \bmod 3$ 。

其中 $w_{X,Y}'$ 表示 X 与 Y 之间的关系。上式可用于维护并查集的合并操作。

设 F1 , F2 分别为 X 和 Y 的父节点（根），则在更新时有 $w_{F1} = w'_{X,Y} + w_Y - w_X$ 。具体证明可以画图易得。

注意实现时需要注意溢出问题，即 $w_{F1} = (w'_{X,Y} + w_Y - w_X + 3) \bmod 3$ 。

查找时我们需要对并查集进行路径压缩。显然此时我们可以通过 $w_Y'' = (w_Y + w_X) \bmod 3$ ，其中 $w''_Y$ 表示更新后的权值，来更新每一个路径。

对于判断每条信息是否矛盾，我们首先需要判断 F1 与 F2 是否在一个集合中。若不在一个集合中，则表明 X 和 Y 之间没有明确的信息表示它们之间的关系，故不矛盾；否则我们需要分情况讨论：

- 若当前信息为 X 和 Y 是同类，则不矛盾时的情况由上表可知需要满足 $w_X = w_Y$ ，故若 $w_X \neq w_Y$ 时信息矛盾；
- 若当前信息为 X 吃 Y ，则不矛盾时的情况由上表可知需要满足 $w_Y - w_X = 1$ 即 $(w_Y - w_X + 3) \bmod 3 = 1$ 时不矛盾，反之则当前信息矛盾。

至此我们就完成了这道题目主体的分析。可以发现，我们事实上通过该并查集维护了一个在 $\bmod 3$ 意义下的整数加法群。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int n, m, ans = 0;
int fa[N], w[N];
/**
 * 0 = SAME
 * 1 = PREDATOR
 * 2 = PREY
 */

int find(int x) {
    if (fa[x] == x) return x;
    int rFa = find(fa[x]);
    w[x] = (w[x] + w[fa[x]]) % 3;
    return fa[x] = rFa;
}

void merge(int u, int v, int weight) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
        /**
         * fu ---> fv
         * ↑       ↑
         * u - - > v
         */
        w[fu] = (weight + w[v] - w[u] + 3) % 3;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (x > n || y > n) {
            ans++;
            continue;
        }
        if (op == 1) {
            int fx = find(x), fy = find(y);
            if (fx == fy && w[x] != w[y]) {
                ans++;
            } else {
                merge(x, y, 0);
            }
        } else {
            int fx = find(x), fy = find(y);
            if (fx == fy && (w[x] - w[y] + 3) % 3 != 1) {
                ans++;
            } else {
                merge(x, y, 1);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
```

### [P1196 [NOI2002] 银河英雄传说](https://www.luogu.com.cn/problem/P1196)

#### 题目大意

在 $[1, 3 \times 10^4]$ 上有分布不同的数列，定义合并操作为将第 $j$ 列的数列的列首接到第 $i$ 列的列尾。

给定 $T$ 个操作，每个操作分为两类：

- 合并操作，将第 $i$ 列的数列合并到第 $j$ 列之后；
- 查询操作，查询编号为 $i$ 的数和 $j$ 的数是否在同一列中，若在同一列中求 $i$ 和 $j$ 之间有多少个数间隔。

保证 $i \neq j$ 。

#### 题目分析

带权并查集。考虑维护每个数所在队列的总长度 $\text{cnt}_i$ 和其到当前队首的距离 $\text{w}_i$ 。

直接维护即可。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 30010;

int T;
int fa[N], w[N], cnt[N];

int find(int x) {
    if (fa[x] == x) return x;
    int rFa = find(fa[x]);
    w[x] += w[fa[x]];
    cnt[x] = cnt[fa[x]];
    return fa[x] = rFa;
}

void merge(int u, int v, int weight) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
        w[fu] += cnt[fv];
        cnt[fu] += cnt[fv];
        cnt[fv] = cnt[fu];
    }
}

int main() {
    cin >> T;
    for (int i = 1; i < N; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    while (T--) {
        char op;
        int i, j;
        cin >> op >> i >> j;
        if (op == 'M') {
            merge(i, j, 1);
        } else {
            int fi = find(i), fj = find(j);
            if (fi != fj) {
                cout << -1 << '\n';
            } else {
                cout << abs(w[i] - w[j]) - 1 << '\n';
            }
        }
    }
    return 0;
}
```

### [P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)

#### 题目大意

给定 $n$ 个节点和 $m$ 条边，求将每个点分配到两个独立的互不相连的图后，两个图中边权的最大值的最小值。

若可以通过一种分配方式使得每个图（森林）中的点互不相连，输出 `0` 。

#### 题目分析

考虑种类并查集。设 `fa[i]` 表示监狱 A ，`fa[i + n]` 表示监狱 B 。

我们不妨对每条边按照边权降序排序，每次对于一条边的两个端点，尝试将其分配到不同的两个集合中。若当前边的两个端点已经在同一集合中，则代表此边为产生冲突的最大边权的最小值。

证明显然。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
struct Relation {
    int a, b, c;

    bool operator > (const Relation x) const {
        return c > x.c;
    }
} relations[N];
int fa[2 * N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void merge(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &relations[i].a, &relations[i].b, &relations[i].c);
    }
    sort(relations + 1, relations + m + 1, greater<Relation>());
    for (int i = 1; i <= 2 * n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        if (find(relations[i].a) == find(relations[i].b) || find(relations[i].a + n) == find(relations[i].b + n)) {
            printf("%d\n", relations[i].c);
            return 0;
        }
        merge(relations[i].a, relations[i].b + n);
        merge(relations[i].a + n, relations[i].b);
    }
    printf("0\n");
    return 0;
}
```

### [P1783 海滩防御](https://www.luogu.com.cn/problem/P1783)

#### 题目大意

给定在纵方向上无限延伸的二维平面 $U$ 和平面内 $m$ 个点，其中每个点可以覆盖以 $k$ 为半径的圆形区域。二维平面的最大横坐标为 $n$ 。求一个最小的 $k$ ，使得这 $m$ 个点覆盖范围所形成的区域的横坐标可以连续覆盖 $[0, n]$ 区间。

精度 $\geq 10^{-2}$ 。

#### 题目分析

考虑二分答案。

对于 `check` 函数，我们不妨对每两个防御塔构成的点对 $(t_i, t_j)$ 按照距离进行排序预处理。对于每次 `check` 操作，假设当前答案为 $x$ ，则我们不妨先选择出所有相距距离 $\leq x$ 的防御塔点对，然后根据每个（已连接或未连接的）防御塔距离两个边界 $(0,0)$ 和 $(n, 0)$ 的大小进行判断是否符合。

我们可以使用并查集来维护该操作。首先先将所有距离 $\leq x$ 的防御塔点对都 `merge` 到相应集合中，然后对于每个需要检查距离边界距离的点对 $(i,j)$ ，若 $i$ 和 $j$ 在同一集合中且 $i$ ，$j$ 均符合距离要求，则当前答案 $x$ 满足条件，缩小右端点；反之亦然。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
constexpr double eps = 1e-4;

int n, m;

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};

struct Point {
    int x, y;

    Point() {}

    Point(int _x, int _y) {
        x = _x, y = _y;
    }

    double distanceFrom(const Point a) const {
        return sqrt(double(x - a.x) * (x - a.x) + double(y - a.y) * (y - a.y));
    }
};

struct Tower {
    int id;
    Point pos;
} a[N];

struct DiffPair {
    Tower u, v;

    bool operator< (const DiffPair a) const {
        return u.pos.distanceFrom(v.pos) < a.u.pos.distanceFrom(a.v.pos);
    }
};

vector<DiffPair> vt;

bool check(double x) {
    DisjointSet ds;
    for (auto pair : vt) {
        if (pair.u.pos.distanceFrom(pair.v.pos) > 2 * x) {
            break;
        }
        ds.merge(pair.u.id, pair.v.id);
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            Tower L = a[i], R = a[j];
            int fL = ds.find(L.id), fR = ds.find(R.id);
            if (L.pos.x <= x && R.pos.x + x >= n && fL == fR) {
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int col, row;
        scanf("%d%d", &col, &row);
        a[i].id = i, a[i].pos.x = col, a[i].pos.y = row;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            vt.push_back(DiffPair{a[i], a[j]});
        }
    }
    sort(vt.begin(), vt.end(), less<DiffPair>());
    double l = 0, r = n;
    while (r - l >= eps) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%.2lf\n", l);
    return 0;
}
```

### [P2502 [HAOI2006] 旅行](https://www.luogu.com.cn/problem/P2502)

#### 题目大意

给定一张 $n$ 个点 $m$ 条边的带权无向图，求一条从节点 $s$ 到节点 $t$ 的路径，使得路径上最大权值与最小权值的比值最小。输出该比值。

数据保证边权均为正数。

#### 题目分析

乍一看很像 Kruskal 重构树，那不妨运用 Kruskal 的部分思路进行求解。

首先，我们可以通过一个并查集来判断 $s$ 与 $t$ 的连通性，若不连通则直接输出 `IMPOSSIBLE` 结束程序。

接下来考虑求解。我们不妨对边按照权值从小到大排序，按照边权大小枚举最小边和最大边。每次扩展最大边时，我们将该边的两端点使用并查集进行连通，若某一时刻 $s$ 与 $t$ 在当前并查集中连通，则尝试更新答案并结束枚举。

该做法正确性显然：选择了最小边、最大边后，我们无需关注中间边的连接方式和边权，因为它们对于最终答案没有贡献。

需要注意的是，存在 $s$ 与 $t$ 仅需要一条边相连的情况。为此，我们只需要将最大边枚举的左边界移动为当前最小边即可。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;

int n, m, s, t;

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
};

struct Edge {
    int u, v, w;

    bool operator <(const Edge a) const {
        return w < a.w;
    }
};
vector<Edge> edge;

DisjointSet ds;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge.push_back(Edge{u, v, w});
        ds.merge(u, v);
    }
    scanf("%d%d", &s, &t);
    if (ds.find(s) != ds.find(t)) {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    sort(edge.begin(), edge.end());
    int maxn = INF, minn = INF;
    double ans = INF;
    for (int i = 0; i < edge.size(); i++) {
        DisjointSet edgeDs;
        for (int j = i; j < edge.size(); j++) {
            Edge minEdge = edge[i], currEdge = edge[j];
            edgeDs.merge(currEdge.u, currEdge.v);
            if (edgeDs.find(s) == edgeDs.find(t)) {
                double curr = (double)currEdge.w / (double)minEdge.w;
                if (curr < ans) {
                    ans = curr;
                    maxn = currEdge.w, minn = minEdge.w;
                }
                break;
            }
        }
    }
    if (maxn % minn == 0) {
        printf("%d\n", maxn / minn);
    } else {
        printf("%d/%d\n", maxn / __gcd(maxn, minn), minn / __gcd(maxn, minn));
    }
    return 0;
}
```

### [P2391 白雪皑皑](https://www.luogu.com.cn/problem/P2391)

#### 题目大意

对一个长度为 $n$ 的序列进行 $m$ 次染色操作，第 $i$ 次染色操作将第 $[(i \times p + q) \bmod n] + 1$ 至第 $[(i \times q + p) \bmod n] + 1$ 个数染色为 $i$ （包括端点）。求 $m$ 次操作之后的染色序列。

初始时染色序列均为 $0$ 。

#### 题目分析

一道使用并查集维护**序列信息**的题目。

我们容易发现一个性质：若从第 $m$ 次操作开始倒序枚举，则每个数仅会被染色一次。我们不妨利用这个性质，记录对于每个节点 $i$ ，其需要被染色的下一个节点 $\text{fa}_i$ 。

考虑使用并查集实现。直接暴力枚举 $m$ 次操作，对于每次操作暴力枚举区间 $[l, r]$ 。设当前数为 $i$ ，则我们从并查集中找到其对应的下一个需要染色的点 $\text{nxt}_i$ 进行跳转。若 $i = \text{nxt}_i$ ，则说明当前节点尚未被染色，我们将其染色后将 $\text{fa}_i$ 与 $\text{fa}_{i + 1}$ 进行合并，代表其下一个需要染色的节点为 $\text{fa}_{i+1}$ 所对应的节点。

由于并查集优秀的传递性，我们可以高效的进行暴力枚举。若并查集实现为渐进 $O(1)$ ，则此实现方法时间复杂度约为 $O(m)$ ，接近线性。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n, m, p, q;

int color[N];

class DisjointSet {
private:
    int fa[N];

public:
    DisjointSet() {
        for (int i = 0; i < N; i++) {
            fa[i] = i;
        }
    }

    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }

    void merge(int u, int v) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            fa[fu] = fv;
        }
    }
} ds;

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    for (int i = m; i >= 1; i--) {
        int l = (i * p + q) % n + 1,
        r = (i * q + p) % n + 1;
        if (l > r) swap(l, r);
        for (int j = l; j <= r;) {
            int nxt = ds.find(j);
            if (nxt == j) {
                color[j] = i;
                ds.merge(j, j + 1);
            }
            j = nxt;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d\n", color[i]);
    }
    return 0;
}
```



浅谈并查集


## 差分约束

差分约束系统是一种特殊的 $n$ 元一次不等式组，形如：
$$
\left\{
\begin{aligned}
&x_i \leq x_j + c_k,\\
&x_{i'} \leq x_{j'} + c_{k'},\\
&\cdots
\end{aligned}
\right.
$$
注意到这与最短路算法中 $\text{dis}_{v} \leq \text{dis}_{u} + w$ 类似。所以我们考虑构造一种特殊的图，使得这个图能够通过某种途径判断它所代表的差分约束系统是否有解。

> 注：若一个差分约束系统有解，则它必有无数个解。
>
> **证明：**若 ${a_1, a_2, \cdots, a_n}$ 为差分约束系统 $U$ 的一组解，则其必有另一组解 ${a_1 + d, a_2 + d, \cdots, a_n + d}$ ，其中 $d \in \R$ 。故得证。

考虑如何求解。我们显然可以通过新建一条边权为 $c_k$ 的边 $E_{j,i}: j \rarr i$ 来表示不等式 $x_i \leq x_j + c_k$ ，以此类推，将每个变量 $x_u$ 看作图中的一个节点，将每个不等式看作图中的一条带权有向边。

由于通过上述方法构造的图无法保证连通，我们不妨设超级源点 $U = x_0$ ，然后从 $U$ 出发向每个节点 $x_i$ （$x_i > 0$） 连接一条边权为 $0$ 的有向边 $E_{0,i}: 0 \rarr i$ 来保证连通性。之后，我们通过从节点 $U$ 开始求单源最短路并检查负环是否存在。若负环存在，则给定的差分约束系统无解；否则 $x_i = \text{dis}_i$ 即为该差分约束系统的一组可能解。

在实现上我们一般采用 SPFA（队列优化的 Bellman-Ford ）作为最短路算法。注意判断负环时因超级源点的存在而导致节点数相应增加。

## 例题

### [P1993 小 K 的农场](https://www.luogu.com.cn/problem/P1993)

#### 题目大意

给定 $n$ 个约束条件，其中分为三类：

- $x_a - x_b \geq c$
- $x_a - x_b \leq c$
- $x_a = x_b$

给定序列 $x_i$ 和 $n$ 个约束条件，求该差分约束系统是否有解。

#### 题目分析

模板题。考虑对于每个操作进行转化，使其成为形如 $x_i \leq x_j + c_k$ 的形式：

- $x_a - x_b \geq c \Rarr x_b \leq x_a - c$
- $x_a - x_b \leq c \Rarr x_a \leq x_b + c$
- $x_a = x_b \Rarr x_a \leq x_b\ ,\ x_b \leq x_a$

最后建边并连接超级源点、检测负环即可。

#### 代码

```cpp
// Problem: P1993 小 K 的农场
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1993
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e5 + 10;

int n, m;
int h[2 * N], vtx[2 * N], nxt[2 * N], w[2 * N], idx, vis[2 * N], dis[2 * N];
int cnt[2 * N], op, a, b, c;
queue<int> q;

void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int tmp = q.front();
        vis[tmp] = 0;
        int p = h[tmp];
        while (p != -1) {
            int v = vtx[p];
            // 此处不能取等，否则会把 0 环判定为负环
            if (dis[tmp] + w[p] < dis[v]) {
                dis[v] = dis[tmp] + w[p];
                cnt[v]++;
                if (cnt[v] > n) return 0;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
            p = nxt[p];
        }
        q.pop();
    }
    return 1;
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> a >> b >> c;
            addEdge(a, b, -c);
        } else if (op == 2) {
            cin >> a >> b >> c;
            addEdge(b, a, c);
        } else {
            cin >> a >> b;
            addEdge(b, a, 0);
            addEdge(a, b, 0);
        }
    }
    for (int i = 1; i <= n; i++) {
        addEdge(n + 1, i, 0);
    }
    if (spfa(n + 1)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}
```

### [P2294 [HNOI2005] 狡猾的商人](https://www.luogu.com.cn/problem/P2294)

#### 题目大意

给定 $m$ 条关于前缀和数组 $c_i$ 的信息，每条信息形如 $c_t - c_{s - 1} = v_k$ ，求该差分约束系统是否有解。

#### 题目分析

根据题目抽象出题目大意后问题就再次转化为裸的差分约束问题，对每条信息可转化为：

- $c_t \leq c_{s - 1} + v_k$
- $c_{s - 1} \leq c_t - v_k$

建边跑最短路即可。注意超级源点。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

struct Edge {
    int v, w;
};

vector<Edge> G[N];
int cnt[N], dis[N], vis[N];
int n, m, T;

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

bool spfa(int u) {
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, 0, sizeof(vis));
    dis[u] = 0, vis[u] = 1;
    q.push(u);
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (auto edge : G[t]) {
            int v = edge.v, w = edge.w;
            if (dis[v] > dis[t] + w) {
                dis[v] = dis[t] + w;
                cnt[v] = cnt[t] + 1;
                if (cnt[v] >= n + 2) {
                    return 1;
                }
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        for (int i = 0; i < N; i++) {
            G[i].clear();
        }
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int s, t, v;
            scanf("%d%d%d", &s, &t, &v);
            // sum[t] - sum[s - 1] = v
            // sum[t] - sum[s - 1] >= v
            // sum[t] - sum[s - 1] <= v
            // sum[s - 1] + v <= sum[t]
            // sum[t] - v <= sum[s - 1]
            addEdge(s - 1, t, v);
            addEdge(t, s - 1, -v);
        }
        for (int i = 0; i <= n; i++) {
            addEdge(n + 1, i, 0);
        }
        bool flag = spfa(n + 1);
        if (flag) {
            printf("false\n");
        } else {
            printf("true\n");
        }
    }
    return 0;
}
```

### [P4878 [USACO05DEC] Layout G](https://www.luogu.com.cn/problem/P4878)

#### 题目大意

给定一个长度为 $n$ 的数列 $a_i$ 和 $m$ 条信息，对于每条信息，有两种可能：

1. $d_a - d_b \leq c_k$
2. $d_a - d_b \geq c_k$

其中 $d_i$ 表示第 $i$ 个数所在的位置。保证数据有序给出。

求 $(d_n - d_1)_{\text{max}}$ 。

#### 题目分析

一个有点意思的题目。

对于判断是否有解的方法显然，套用差分约束模板即可。在此主要探讨关于求解 $(d_n - d_1)_{\text{max}}$ 。

显然我们无法直接使用由超级源点 $U$ 出发的最短路数组（正权均被设为 $0$ ），不妨在有解的情况下从结点 $1$ 开始跑第二次最短路，此时的 $\text{dis}$ 数组即为 $1$ 出发可到达的节点的最短路，即为差分约束系统的部分可能解。若 $\text{dis}_n = +\infin$ ，则代表从 $1$ 没有相应的条件指向 $n$ ，此时两者可以相距正无穷远（即为输出 `-2` 时的情况）。

这道题还有一个细节需要注意。题目明确，可以有多个奶牛在同一位置上，即两个相邻奶牛最小距离 $\geq 0$ 。即 $d_i - d_{i - 1} \geq 0$ 也需要作为差分约束系统的条件之一参与决策。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;

int n, ml, md;

struct Edge {
    int v, w;
};
vector<Edge> G[N];

int cnt[N], dis[N], vis[N];

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

bool spfa(int s) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto [v, w] : G[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n + 1) {
                    return 0;
                }
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

int main() {
    scanf("%d%d%d", &n, &ml, &md);
    for (int i = 1; i <= ml; i++) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        // s_b - s_a <= d
        // s_b <= s_a + d
        addEdge(a, b, d);
    }
    for (int i = 1; i <= md; i++) {
        int a, b, d;
        scanf("%d%d%d", &a, &b, &d);
        // s_b - s_a >= d
        // s_a <= s_b - d
        addEdge(b, a, -d);
    }
    for (int i = 2; i <= n; i++) {
        // s_i - s_i-1 >= 0
        // s_i-1 <= s_i - 0
        addEdge(i, i - 1, 0);
    }
    for (int i = 1; i <= n; i++) {
        addEdge(0, i, 0);
    }
    bool flag = spfa(0);
    if (flag) {
        spfa(1);
        if (dis[n] == INF) {
            printf("-2\n");
        } else {
            printf("%d\n", dis[n]);
        }
    } else {
        printf("-1\n");
    }
    return 0;
}
```



浅谈差分约束


乘法逆元在 OI 中有非常重要的用途，通常用来快速求解模意义下大数除法问题。本文将简单讨论有关乘法逆元的求解方法和题目。

## 线性同余方程

在了解乘法逆元概念之前，我们需要先了解一个前置概念：线性同余方程。

形如 $ax \equiv b \pmod n$ 的方程称为**线性同余方程**。其中 $a,b,n$ 为给定整数，$x$ 为未知数。

### 同余

所谓同余，即两个数对同一个数取模有相同的余数。例如 $a \equiv b \pmod p$ 就意味着 $a$ 、$b$ 除以 $p$ 的余数相同。形式化地， $a - b = km$ 为 $a \equiv b \pmod m$ 的充要条件，其中 $k \in \Z$ 。

具象化地，若 $a \equiv b \pmod m$ ，则 $a$ 、$b$ 在$\bmod m$ 意义下是等价的。

同余有如下性质：

- 自反性：$a \equiv a \pmod m$ ；
- 对称性：$a \equiv b \pmod m \Leftrightarrow b \equiv a \pmod m$ ；
- 传递性：$a \equiv b \pmod m ,\ b \equiv c \pmod m \Rightarrow a \equiv c \pmod m$ ；
- 相加：$a \equiv b \pmod m, \ c \equiv d \pmod m \Rightarrow a \pm c \equiv b \pm d \pmod m$ ；
- 相乘：$a \equiv b \pmod m, \ c \equiv d \pmod m \Rightarrow ac \equiv bd \pmod m$ ；
- 幂运算：$a \equiv b \pmod m \Rightarrow a^n \equiv b^n \pmod m$ ；
- ……

我们考虑求解上述线性同余方程。我们可以发现，上述同余方程等价于如下线性不定方程：
$$
ax + nk = b
$$
其中 $x$ 、$k$ 为未知数，当且仅当 $\gcd(a,n) \mid b$ 时上述方程有整数解。

### 扩展欧几里得算法

我们知道，在基本欧几里得算法中，我们通过辗转相除法来求解 $\gcd(a,n)$ 。具体地，基本欧几里得算法有递归式 $\gcd(a,n) = \gcd(n, a \bmod n)$ ，直到 $a \bmod n = 0$ 。

扩展欧几里得算法的扩展在于，它可以在计算 $\gcd(a,n)$ 的基础上求得一组对于方程 $ax + nk = \gcd(a,n)$ 的整数特解。我们称上述方程 $ax + nk = \gcd(a,n)$ 为**贝祖等式**。

扩展欧几里得算法使用了递归的思想求解。我们不妨设已知等式：
$$
nx_1 + (a \bmod n)k_1 = \gcd(n, a \bmod n)
$$
容易发现，$a \bmod n = a - \lfloor\frac{a}{n} \rfloor \times n$ 。则上述等式化为：
$$
nx_1 + (a - \lfloor \frac{a}{n} \rfloor \times n)k_1 = \gcd(n, a\bmod n)
$$
整理得：
$$
ak_1 + n(x_1 - \lfloor \frac{a}{n} \rfloor \times k_1) = \gcd(a,n)
$$
则我们可以求得新的解 $x = k_1$ ，$y = x_1 - \lfloor \frac{a}{b} \rfloor \times k_1$ 。

#### 具体过程

设要计算 $\gcd(a,n)$ 和贝祖等式 $ax + nk = \gcd(a,n)$ 的特解 $x_0$ ，$k_0$ 。

首先，若 $n = 0$ ，则按照基本欧几里得算法，有 $\gcd(a,n) = a$ ，且 $x_0 = 1$ ，$k_0 = 0$ 。递归终止。

我们考虑计算。按照上述推导，我们可以发现 $\gcd(n, a \bmod n) = nx_1 + (a \bmod n)k_1$ ，且当前 $x_0 = y_1$ ，$k_0 = x_1 - \lfloor \frac{a}{n} \rfloor \times k_1$ 。

#### 代码实现

```cpp
int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}
```

### 扩展欧几里得算法求解线性同余方程

我们继续考虑求解线性同余方程 $ax \equiv b \pmod n$ 的转化形式：
$$
ax + nk = b \tag{1-1}
$$

我们已知可以求解出方程
$$
ax_0 + nk_0 = \gcd(a,n) \tag{1-2}
$$
的一组特解。考虑对 $\text{(1-2)}$ 式进行转化。等式两边同时乘以 $\frac{b}{\gcd(a,n)}$ ，得：
$$
a\frac{b}{\gcd(a,n)}x_0 + n\frac{b}{\gcd(a,n)}k_0 = b
$$
则原方程有特解 $x = \frac{b}{\gcd(a,n)}x_0$ ，$k = \frac{b}{\gcd(a,n)}k_0$ 。

考虑求得通解。显然，若 $\gcd(a,n) = 1$ ，且方程 $ax + nk = b$ 有特解 $X_0$ ，$K_0$ ，则我们可以求出该方程的任意解：
$$
\left\{
\begin{aligned}
&x = X_0 + nt,\\
&k = K_0 - at
\end{aligned}
\right.
$$
其中 $t \in \Z$ 。如果要求最小正整数解，则 $x = X_0 \bmod t$ ，其中 $t = \frac{n}{\gcd(a,n)}$ 。若 $n$ 为质数，则 $x = X_0 \bmod n$ 。

#### 代码实现

```cpp
int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
      x = 1;
      y = 0;
      return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}

bool liEu(int a, int b, int c, int& x, int& y) {
    int d = ex_gcd(a, b, x, y);
    if (c % d != 0) return 0;
    int k = c / d;
    x *= k;
    y *= k;
    return 1;
}
```

## 乘法逆元

指模意义下的乘法逆元。

### 定义

如果有 $x$ 满足线性同余方程 $ax \equiv 1 \pmod b$ ，则 $x$ 被称为 $a \bmod b$ 的逆元，记作 $x = a^{-1}$ 。

在实数意义下，$a$ 的逆元即为 $a$ 的倒数 $\frac{1}{a}$ 。在模意义下，$x$ 的逆元 $x^{-1}$ 在模意义下的运算类似于 $\frac{1}{x}$ 。

### 求解

#### 扩展欧几里得求逆元

显然我们可以选择求解上述线性同余方程。直接套用扩展欧几里得算法即可。

```cpp
void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
```

#### 线性求连续序列的逆元

如果要选择求解 $1,2,\dots,n$ 中每个数关于某个模数的逆元，扩展欧几里得算法就会出现很多冗杂的计算，导致时间复杂度偏高。

考虑线性递推求解。我们显然可以注意到一个重要前提：
$$
1^{-1} \equiv 1 \pmod p
$$
证明显然：$1 \times 1 \equiv 1 \pmod p$ 对于任意 $p \in \Z$ 恒成立，$1$ 在$\bmod p$ 意义下的逆元恒为 $1$ 。

假设我们现在要计算 $i$ 的逆元 $i^{-1}$ ，即求出 $i^{-1} \times i \equiv 1 \pmod p$ 的解 $i^{-1}$ 。

令 $k = \lfloor\frac{p}{i} \rfloor$ ，$j = p \bmod i$ 。则 $p = ki + j$ 。即 $ki + j \equiv 0 \pmod p$ 。

两边同时乘以 $i^{-1} \times j^{-1}$ ，有：
$$
kj^{-1} + i^{-1} \equiv 0 \pmod p
$$
移项，有
$$
i^{-1} \equiv -kj^{-1} \pmod p
$$
代入 $k = \lfloor\frac{p}{i}\rfloor$ ， $j = p \bmod i$ ，有
$$
i^{-1} \equiv -\lfloor\frac{p}{i}\rfloor \times (p \bmod i)^{-1} \pmod p
$$
不难发现 $p \bmod i < i$ ，即计算 $i^{-1}$ 时已经算出 $(p \bmod i)^{-1}$ ，可以递推求解。

形式化地，我们有：
$$
i^{-1} = \left \{
\begin{aligned}
&1,&& \text{if}\quad i = 1,\\
&-\lfloor\frac{p}{i}\rfloor \times (p \bmod i)^{-1}, &&\text{otherwise.}\\
\end{aligned}
\right. \pmod p
$$
具体实现如下：

```cpp
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (long long)(p - p / i) * inv[p % i] % p;
}
```

注意我们使用 $p - \lfloor\frac{p}{i}\rfloor$ 来防止出现负数。

#### 线性求任意 $n$ 个数的逆元

考虑前缀积。我们计算出 $n$ 个数 $a_1,a_2,\dots,a_n$ 的前缀积 $s_i$ ，然后使用扩展欧几里得算法计算 $s_n$ 的逆元 $s_n^{-1}$ 。

我们不妨抽象理解为实数意义下的逆元，即 $s_n^{-1} = \frac{1}{s_n} \pmod p$ 。

又 $s_n = s_1 \times s_2 \times \dots \times s_n$ ，则 $s_n^{-1} = \frac{1}{s_1 \times s_2 \times \dots \times s_n} \pmod p$ 。将 $s_n^{-1}$ 乘上 $s_n$ ，我们即可得到 $s_{n - 1}^{-1}$ 。如此递推可求得所有 $s_i^{-1}$ 。

对于 $a_i^{-1}$ ，我们显然有：
$$
a_i^{-1} \equiv s_{i - 1} \times s_{i}^{-1} \pmod p
$$

```cpp
s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = exgcd(s[n], p);
// sv_i 即为 s_i 的逆元
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;
```

总时间复杂度为 $O(n + \log p)$ 。

## 题目

### [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082)

模板题，套用扩展欧几里得算法即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int a, n;

int exgcd(int a, int n, int& x, int& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    int t = exgcd(n, a % n, x, k);
    int xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

int main() {
    scanf("%d%d", &a, &n);
    int x, k;
    int t = exgcd(a, n, x, k);
    t = n / t;
    printf("%d\n", (x % t + t) % t);
    return 0;
}
```

### [P5431 【模板】模意义下的乘法逆元 2](https://www.luogu.com.cn/problem/P5431)

模板题，使用线性乘法逆元模板带入求解即可。注意快速输入输出和 `long long` 。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;

long long n, p, K;
long long a[N], s[N], sv[N];

long long read() {
	long long x=0,flag=1;char c;
	while ((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
	while (c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*flag;
}

int exgcd(int a, int n, int& x, int& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    int t = exgcd(n, a % n, x, k);
    int xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

int main() {
    s[0] = 1;
    n = read(); p = read(); K = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        s[i] = s[i - 1] * (a[i] % p) % p;
    }
    int x, k;
    int b = exgcd(s[n], p, x, k);
    b = p / b;
    sv[n] = (x % b + b) % b;
    for (int i = n; i >= 1; i--) {
        sv[i - 1] = sv[i] * a[i] % p;
    }
    long long ans = 0, t = 1, inv;
    for (int i = 1; i <= n; i++) {
        t = t * K % p;
        inv = sv[i] * s[i - 1] % p;
        ans = (ans + inv * t % p) % p;
    }
    printf("%lld\n", ans);
    return 0;
}
```

### [P2054 [AHOI2005] 洗牌](https://www.luogu.com.cn/problem/P2054)

#### 题目大意

给定一个序列 $a_i$ ，其中 $1 \leq i \leq n$ 且 $n$ 为偶数。对于每次操作，将序列分为 $a_1 \sim a_{\frac{n}{2}}$ 和 $a_{\frac{n}{2} + 1} \sim a_n$ 两部分。对于前半部分的元素 $a_i$ ，其在新序列中的位置为 $2i$ ；对于后半部分的元素 $a_j$ ，其在新序列中的位置为 $2j - (n + 1)$ 。

现在给定 $n$ 和操作次数 $m$ ，求经过 $m$ 次操作后位于第 $L$ 个位置上的元素在初始序列中的位置 $x$ 。

其中 $1 \leq n \leq 10^{10}$ ，$0 \leq m \leq 10^{10}$ 且 $n$ 为偶数。

#### 分析

对于序列中任意元素 $a_i$ ，考虑其在新序列中的位置。显然其在新序列中的位置为 $2i \bmod (n + 1)$ 。

我们容易发现，经过 $m$ 次变换后，其最终位置为 $i \cdot 2^m \bmod (n + 1)$ 。则易得如下同余方程：
$$
x \cdot 2^m \equiv L \pmod{n + 1}
$$
则有
$$
x \equiv \frac{L}{2^m} \pmod{n + 1}
$$
考虑乘法逆元。设 $2$ 在$\bmod{n + 1}$ 意义下的乘法逆元为 $k$ ，则有
$$
x \equiv k^m \cdot L \pmod{n + 1}
$$
得解。

对于 $2$ 在模意义下的乘法逆元 $k$ ，我们显然可以通过扩展欧几里得算法在 $O(\log n)$ 时间内求解。

注意到 $n \leq 10^{10}$ ，需要使用快速幂求解 $k^m$ 。这里介绍一下快速乘：一个对于模意义下大数乘法的快速计算方法，原理类似快速幂。具体操作是维护一个被乘数 $a$ ，将其按二进制位依次乘到乘数 $b$ 中，计算时逐步取模。

详细参见 <https://leungll.site/2021/05/24/ksm-permalink/> 和 [https://oi-wiki.org/math/binary-exponentiation](https://oi-wiki.org/math/binary-exponentiation/#%E6%A8%A1%E6%84%8F%E4%B9%89%E4%B8%8B%E5%A4%A7%E6%95%B4%E6%95%B0%E4%B9%98%E6%B3%95) ，存在在 `long long` 范围内的 $O(1)$ 快速解法。下面的程序使用朴素的 $O(\log_2 m)$ 的普通快速乘。

#### 代码

注意 `long long` 和取模。数据范围较大，也需要注意常数优化。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

long long n, m, L;

long long exgcd(long long a, long long n, long long& x, long long& k) {
    if (n == 0) {
        x = 1, k = 0;
        return a;
    }
    long long t = exgcd(n, a % n, x, k);
    long long xx = x;
    x = k, k = xx - a / n * k;
    return t;
}

long long qmul(long long a, long long b, long long mod) {
    long long ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

long long qpow(long long a, long long b, long long mod) {
    long long ans = 1, base = a;
    while (b) {
        if (b & 1) {
            ans = qmul(ans, base, mod);
        }
        base = qmul(base, base, mod);
        b >>= 1;
    }
    return ans;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &L);
    long long x, k;
    long long t = exgcd(2, n + 1, x, k);
    t = (n + 1) / t;
    long long inv2 = (x % t + t) % t;
    printf("%lld\n", qmul(L, qpow(inv2, m, n + 1), n + 1));
    return 0;
}
```



浅谈乘法逆元


## 基础概念

- 样本点：随机试验中可能发生的结果
- 样本空间：所有样本点的集合，记作 $\Omega$
- 概率：记作 $P(A)$ ，即事件 $A$ 发生的概率，满足 $P(A) \in \R 且 0\leq P(A) \leq 1$

## 概率模型

### 古典模型

即各个事件出现的概率相等。此时 $P(A) = \frac{A 包含的基本事件总数}{基本事件总数}$ 。典型的例子包括抛硬币、掷骰子等。

**例：一年有 365 天，每个人出生日期都是随机的。班里有 30 名同学，则存在两位同学生日相同的概率是多少？**

**解：** 每个人的生日有 365 种可能性，基本事件总数即为 $365^{30}$ 。等概率随机即满足古典概型。显然直接计算概率需要考虑只有两个同学生日相同、只有三个同学生日相同等情况，计算复杂。考虑转化。

我们不妨计算上述命题的逆命题，即不存在两位同学生日相同的概率有多少。此时每位同学的生日都互不相同，所有可能的情况即为 $A^{30}_{365}$ 种。则该逆命题的概率为 $P(不存在两位同学生日相同) = \frac{A^{30}_{365}}{365^{30}}$ 。

则原问题的答案为 $P(存在两位同学生日相同) = 1 - \frac{A^{30}_{365}}{365^{30}}$ 。

### 几何概型

如果每个事件发生的概率只与构成该事件区域的长度（面积或体积或度数）成比例，则称这样的概率模型为几何概率模型，简称为几何概型。[^1]

简单来说，在几何概型下，随机试验的所有可能结果（即基本事件总数）为 $\infty$ 且每个事件发生的概率均等。典型的例子包括在一个几何区域内随机取一点进行实验、一个人到单位的时间（在 8:00 ~ 9:00 之间的任意时刻）等。

**例：0 时刻时甲乙两人开始等车，甲的车在前 60 min 内随机时刻会到，乙的车在前 120 min 内随机时刻会到。求甲比乙早上车的概率。**

**解：** 设甲的车在 $X$ 时刻会到，乙的车在 $Y$ 时刻会到。则满足 $0 \leq X \leq 60$ ，$0 \leq Y \leq 120$ 。

显然我们要计算的是 $X < Y$ 的概率。不妨用坐标系来表示 $X,Y$ ：

![geometric-probability](https://blog.samzhangjy.com/assets/posts/probability-theory/geometric-probability.png)

那么，我们要求的 $X < Y$ 可以分为两部分： $0 \leq Y \leq 60$ 时和 $60 < Y \leq 120$ 时。显然第二个区间永远满足 $X < Y$ 。

对于 $0 \leq Y \leq 60$ 时，显然我们可以将图像化为两个三角形。对于上半部分的三角形，永远满足 $X < Y$ 。

综上， $X < Y$ 在坐标轴图像上表现为图中的阴影区域。让我们来计算一下其发生的概率：
$$
P(甲比乙早上车) = P(X < Y) = \frac{60 \times 60 + \frac{1}{2} \times 60 \times 60}{60 \times 120} = \frac{3}{4} = 75\%
$$
即有 75% 的概率甲比乙早上车。

### 条件概率

即事件 $A$ 在事件 $B$ 发生的条件下发生的概率，记作 $P(A|B)$ 。要计算条件概率，我们需要引入两个概念：

- **联合概率** 表示两个事件共同发生的概率，记作 $P(A \cap B)$ 或 $P(A,B)$ 或 $P(AB)$ ；
- **边缘概率** 表示某个事件发生的概率，记作 $P(A)$ 。

条件概率 $P(A|B) = \frac{P(A \cap B)}{P(B)}$ 。特别地，若 $A$ 、$B$ 为两个独立事件，则 $P(A \cap B) = P(A) \times P(B)$ ，则 $P(A | B) = P(A)$ ， $P(B|A) = P(B)$ 。

**例 1 ：一对夫妻生了两个孩子，第一个孩子是女孩，求第二个孩子是女孩的概率。**

**解 1 ：** 显然这两个事件是独立事件，故 $P(第二个孩子是女孩)= \frac{1}{2}$ 。

**例 2 ：一对夫妻生了两个孩子，其中一个孩子是女孩，求另一个孩子也是女孩的概率。**

**解 2 ：** 存在四个基本事件：（男，男）、（男，女）、（女，男）、（女，女）。

则 $P(一个孩子是女孩|另一个孩子也是女孩) = \frac{P(一个孩子是女孩 \cap 另一个孩子也是女孩)}{P(另一个孩子是女孩)} = \frac{\frac{1}{4}}{\frac{3}{4}} = \frac{1}{3}$ 。

#### 贝叶斯公式

$$
P(A|B) = \frac{P(A \cap B)}{P(B)} = \frac{P(B | A) \times P(A)}{P(B)}
$$

推导证明显然。

**例：某种疾病发病率为 $0.01\%$ ，通过某种检测方式可以检测该疾病。若某人患病，则检测结果为阳性的概率为 $99\%$ ；若没有患病，则检测出阳性的概率是 $1\%$ 。求某人检测结果为阳性时患病的概率。**

**解：** 根据题意，易得
$$
P(患病|检测阳性) = \frac{P(患病 \cap 检测阳性)}{P(检测阳性)}
$$
即
$$
P(患病|检测阳性) = \frac{P(检测阳性|患病) \times P(患病)}{P(检测阳性)} = \frac{0.99 \times 0.0001}{0.99 \times 0.0001 + 0.9999 \times 0.01} \approx 0.98\%
$$

### 应用

#### 看电影

在一个电影院举办针对儿童的六一儿童节免费观影活动，有两个影院放映不同的电影，观影儿童通过投掷硬币决定进入哪一个电影院，投到正面的进入 A 影院，反面的进入 B 影院。 两个影院都能容纳 $n$（$0 \leq n \leq 1000$）个人,预计有 $2n$ 个儿童观影。如果一个影院人满了，则接下来的儿童直接进入另一个影院无需投掷硬币。

求排在队尾的两个儿童同时进入同一个影院的概率。

##### 解法一

考虑通过组合数学求解。

显然直接计算进入同一个影院的概率较为复杂，不妨转化为求解进入不同影院的概率。则一个影院内儿童的所有可能情况有 $C^{n - 1}_{2n - 2}$ 种可能，另一个影院的儿童也随之确定。又因为总事件数为 $2^{2n - 2}$ ，故概率为

$$
P(在队尾的两个儿童进入不同影院) = \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}
$$

则所求概率为

$$
P(在队尾的两个儿童进入相同影院) = 1 - \frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}}
$$

又
$$
\begin{align}
\frac{C^{n - 1}_{2n - 2}}{2^{2n - 2}} &= \frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} ÷ 4^{n - 1}\\
&=\frac{(2n - 2)!}{(n - 1)! \times (n - 1)!} \times \frac{1}{4^{n - 1}}\\
&=\frac{2n - 2}{4(n - 1)} \times \frac{2n - 3}{4(n - 2)} \times \cdots \times \frac{n}{4 \times 1}
\end{align}
$$
故程序如下：

```cpp
int main() {
    int n;
    cin >> n;
    n >>= 1;  // 输入为2n
    double ans = 1.0;
    for(int i = 1; i < n; i++)
        ans = ans * (i + n - 1) / (i << 2);  // 时间复杂度O(n)
    printf("%.4lf", 1 - ans);
    return 0;
}
```

##### 解法二

考虑使用动态规划。

定义 $f_{n,m}$ 表示影院 A 剩下 $n$ 个位置，影院 B 剩下 $m$ 个位置时最后两个儿童进入同一个影院的概率。

考虑状态转移。显然 $f_{n,m}$ 由 $f_{n - 1,m}$ 或 $f_{n, m - 1}$ 转移而来，则 $f_{n,m} = \frac{1}{2} \times f_{n -  1, m} + \frac{1}{2} \times f_{n, m - 1}$ 。即当前状态为先前两个状态随机 50% 决定。

显然，对于 $0 < n \leq 1$ 或 $0 < m \leq 1$ ，$f_{n,m} = 0$ 。即当剩余座位 $\leq 1$ 时两个人不能同时进入一个影院。

同理，当 $n = 0$ 或 $m = 0$ 时，两人必须进入同一个影院，即 $f_{n,m} = 1$ 。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;

int n;
double f[N][N];

int main() {
    scanf("%d", &n);
    n /= 2;
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[0][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = 0.5 * (f[i - 1][j] + f[i][j - 1]);
        }
    }
    printf("%.4lf", f[n][n]);
    return 0;
}
```

#### [Sushi](https://www.luogu.com.cn/problem/AT_dp_j)

现有$N(1 ≤ N ≤ 300)$个盘子，编号为$1,2,3,…,N$。第$i$个盘子中放有$a_i(1≤a_i ≤3)$个寿司。

接下来每次执行以下操作，直至吃完所有的寿司。从第$1,2,3,…,N$个盘子中任选一个盘子，吃掉其中的一个寿司。若没有寿司则不吃。

若将所有寿司吃完，请问此时操作次数的数学期望是多少？

考虑概率 DP 。我们设状态 $f_{i,j,k,l}$ 代表剩余 1、2、3、0 个寿司的盘子的数量为 $i,j,k,l$ 时期望的操作数。

注意到 $l = n - i - j -k$ ，故优化为 $f_{i,j,k}$ 。时间复杂度 $O(300^3) = 2.7 \times 10^7 < 10^8$ ，能过。

考虑状态转移。容易发现对于每一个状态都是由上一个状态吃掉某盘中的一个寿司得来的。故易得
$$
f_{i,j,k} = f_{i,j,k} \times \frac{n - i - j -k}{n} + f_{i - 1,j,k} \times \frac{i}{n} + f_{i + 1,j - 1,k} \times \frac{j}{n} + f_{i,j - 1,k+1} \times \frac{k}{n} + 1
$$
移项通分，得
$$
f_{i,j,k} = f_{i-1,j,k} \times \frac{i}{i + j +k} + f_{i + 1,j - 1,k} \times \frac{j}{i + j + k} + f_{i,j + 1,k - 1} \times \frac{k}{i + j + k} + \frac{n}{i + j + k}
$$
考虑初始状态。显然当所有盘子的寿司都为空时期望操作数为 $0$ ，即 $f_{0,0,0} = 0$ 。

考虑答案。显然答案为 $f_{b_1,b_2,b_3}$ ，其中 $b_i$ 代表初始状态时有 $i$ 个寿司的盘子数量。

需要注意的是，本题为了满足无后效性需要从 $k$ 到 $i$ 倒序枚举。

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 310;

double f[N][N][N];
double n, a[N];
int b[10];

int main() {
    scanf("%lf", &n);
	for (int i = 1; i <= n; i++) {
        scanf("%lf", &a[i]);
		b[(int)a[i]]++;
	}
    f[0][0][0] = 0;
    for (int k = 0; k <= n; k++) {
        for (int j = 0; j <= n; j++) {
            for (int i = 0; i <= n; i++) {
                if (!(i || j || k)) continue;
                if (i >= 1) f[i][j][k] += f[i - 1][j][k] * (double)i / (double)(i + j + k);
                if (j >= 1) f[i][j][k] += f[i + 1][j - 1][k] * (double)j / (double)(i + j + k);
                if (k >= 1) f[i][j][k] += f[i][j + 1][k - 1] * (double)k / (double)(i + j + k);
                f[i][j][k] += (double)n / (double)(i + j + k);
            }
        }
    }
    printf("%.15lf\n", f[b[1]][b[2]][b[3]]);
	return 0;
}
```



[^1]: https://baike.baidu.com/item/%E5%87%A0%E4%BD%95%E6%A6%82%E5%9E%8B/4035773

浅谈概率


## 什么是分层图？

所谓分层图，即通过构建一张新图使得一张图有多个维度。一个典型的例子是使一张图复制出一份或多份，并在复制出的不同的层之间根据要求连接某些点。

一个典型的应用就是在不同路径上有 $k$ 个决策 $p_1,p_2,p_3$ ，那么对于每个决策 $p_i$ ，我们构建一层新的图使得边 $E(u,v)$ 可以用来表示决策 $p_i$ 。后续的操作经常使用最短路/最长路相关算法求解。

## 例题

### [P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)

#### 题目概述

给定一个包含 $n$ 个节点和 $m$ 条边的带权无向图 $G$ （节点由 $0 \sim n - 1$ 编号）和 $k$ 次决策（$0 \leq k \leq 10$），对于每个决策 $D_i$ ，可以以 $0$ 为边权通过任意一条边一次。求从节点 $s$ 到 $t$ 的最小花费。

#### 分析

容易发现在不考虑进行决策的情况下（即 $k=0$ 时），题目转化为求无向图上的最短路径。显然可以通过 Dijkstra 等算法在 $O(m \log m)$ 时间内解决。

![layered-graph-1](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-1.png)

考虑进行决策。对于每一条边，我们都可以有选择按照原有边权走或者按边权为 $0$ 走两种选择。显然后者只能选择**最多** $k$ 次（**不一定要全选完 $k$ 次**）。那么，我们不妨对于每条边 $E(u,v,w)$ 增设一个决策边 $E'(u,v,0)$ ，即选择走边 $E'$ 意味在边 $E$ 上进行一次决策。

![layered-graph-2](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-2.png)

接下来我们需要考虑限定 $k$ 次决策。容易发现，在上图中，我们在下层新建了 $n$ 个节点 $V_0' \sim V_1'$ ，并将决策边的终点设在了第二层对应点上。这样，对于每一次决策，我们都可以保证单向性（上层的点只能到达下层）。同时，因为每一层的节点之间都有来自原始图的连边，所以不会影响正常边的统计。

显然，对于 $k$ 次决策，我们只需要建立 $k$ 层上述的图即可。

![layered-graph-3](https://blog.samzhangjy.com/assets/posts/layered-graph/layered-graph-3.png)

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m, K, s, t;

struct Edge {
    int v, w;
};
vector<Edge> G[N];
int dis[N], vis[N];

void addEdge(int u, int v, int w) {
    G[u].push_back(Edge{v, w});
}

void dijkstra(int u) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    struct Node {
        int dis, u;

        bool operator>(const Node& a) const {
            return dis > a.dis;
        }
    };
    priority_queue<Node, vector<Node>, greater<Node>> q;
    q.push(Node{0, u});
    dis[u] = 0;
    while (!q.empty()) {
        Node curr = q.top();
        q.pop();
        int u = curr.u;
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto edge : G[u]) {
            int v = edge.v, w = edge.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(Node{dis[v], v});
            }
        }
    }
}

int main() {
    for (int i = 0; i < N; i++) G[i].clear();
    scanf("%d%d%d", &n, &m, &K);
    scanf("%d%d", &s, &t);
    s++, t++;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u++, v++;
        addEdge(u, v, w);
        addEdge(v, u, w);
        for (int i = 1; i <= K; i++) {
            int uu = i * n + u, vv = i * n + v;
            addEdge(uu, vv, w);
            addEdge(vv, uu, w);
            addEdge((i - 1) * n + u, vv, 0);
            addEdge((i - 1) * n + v, uu, 0);
        }
    }
    dijkstra(s);
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= K; i++) {
        ans = min(ans, dis[i * n + t]);
    }
    printf("%d\n", ans);
    return 0;
}
```

需要注意的是，在统计答案时我们需要在 $k$ 层中取最小值，因为不一定需要 $k$ 次决策才能到达终点。

### [P3119 [USACO15JAN] Grass Cownoisseur G](https://www.luogu.com.cn/problem/P3119)

#### 题目概述

给定一个 $n$ 个点 $m$ 条边的有向图 $G$ 和 $1$ 次决策，求从 $1$ 号节点返回到 $1$ 号节点的最长路。

定义一次决策为将任意一条边 $E(u,v)$ 变为 $E'(v, u)$ 。

#### 分析

考虑建图。显然可以将决策转化为分层图求解。

对于原图 $G$ ，我们新建一个图 $G'$ 使得 $G'=G$ 。然后，我们对于 $E(u,v) \in G$ ，$E'(u',v') \in G'$ 间建立有向边 $E''(v, u')$ ，即对于原图和复制图中的每个点之间建立反向边。

然后可以考虑求最长路。显然上述做法建出来的图无法保证是 DAG ，故先进行 Tarjan 缩点后重新建带权图，最后使用拓扑排序求最长路。

#### 代码

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
int dfn[N], low[N], color[N], sccCnt = 0, idx = 0, vis[N];
set<int> scc[N];
stack<int> s;
int dis[N], inDegree[N];

class Graph {
  private:
    vector<int> G[N];

  public:
    int inDegree[N];

    void addEdge(int u, int v) {
        G[u].push_back(v);
        inDegree[v]++;
    }

    vector<int> operator[](int x) {
        return G[x];
    }
} G, G2;

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    vis[u] = 1;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            scc[sccCnt].insert(x);
            color[x] = sccCnt;
            vis[x] = 0;
            if (u == x) break;
        }
    }
}

void toposort(int s) {
    queue<int> q;
    for (int i = 1; i <= sccCnt; i++) {
        if (G2.inDegree[i] == 0) q.push(i);
    }
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto v : G2[u]) {
            G2.inDegree[v]--;
            if (G2.inDegree[v] == 0) {
                q.push(v);
            }
            if (dis[u] >= 0) dis[v] = max(dis[v], dis[u] + (int)scc[v].size());
        }
    }
}

int main() {
    memset(dis, -0x3f, sizeof(dis));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.addEdge(u, v);
        G.addEdge(v, u + n);
        G.addEdge(u + n, v + n);
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int u = 1; u <= 2 * n; u++) {
        for (auto v : G[u]) {
            if (color[u] == color[v]) continue;
            G2.addEdge(color[u], color[v]);
        }
    }
    toposort(color[1]);
    printf("%d\n", max(dis[color[1]], dis[color[1 + n]]));
    return 0;
}
```

## 总结

分层图是一种实用的建图思想，可以解决多种图上决策问题。实际使用中需要注意层与层之间的联系，必要时可结合 Tarjan 缩点后处理。

浅谈分层图最短路


## 强连通分量

有向图 G 强连通是指，G 中任意两个结点连通。

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。

## 原理

Tarjan 算法是一种基于 DFS 生成树的回溯算法。在递归搜索图的过程中，Tarjan 主要维护了以下两个变量：

- `dfn[i]` ：时间戳，即按 DFS 序遍历到节点 $i$ 的次序；
- `low[i]` ：在以节点 $i$ 为根的子树中，能够回溯到且仍在栈中的节点的最小时间戳。

其中，在搜索过程中，设当前节点为 $u$ ，会遇到如下情况：

- $u$ 未被访问过：搜索 $u$ 的子树，并用 `low[u]` 更新 `low[i]` ；
- $u$ 已经被访问过，但仍在栈中：用 `dfn[u]` 更新 `low[i]` ；
- $u$ 已经被访问过，且不在栈中：说明 $u$ 所在强连通分量已经搜索完毕，无需做任何操作。

显然，当 `low[i] = dfn[i]` 时，存在一个以 $i$ 为根的强连通分量。我们将 $i$ 及在 $i$ 之后入栈的节点依次出栈并记录，此时这些节点所构成的强连通图即为原图 $G$ 的一个强连通分量。

## 实现

```cpp
int low[N], dfn[N], color[N], idx = 0, sccCnt = 0;
stack<int> s;
set<int> scc[N];

void tarjan(int u) {
    low[u] = dfn[u] = ++idx;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            color[x] = sccCnt;
            scc[sccCnt].insert(x);
            if (x == u) break;
        }
    }
}

int main() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    return 0;
}
```

其中，`color[i]` 表示节点 $i$ 所在强连通分量编号，`sccCnt` 表示强连通分量个数。

set `scc[i]` 中存储了编号为 $i$ 的强连通分量所包含的节点。

## 缩点与重新构图

在一些题目中，存在着由多个节点构成的环或连通图。由于强连通分量内每个节点互相可达，我们常常需要使用 Tarjan 或类似算法将这些强连通分量缩为一个点以便使用其他算法求解。这个过程就是**缩点**。

### P2341 受欢迎的牛

题目链接：<https://www.luogu.com.cn/problem/P2341>

在这道题中，奶牛之间的关系显然可以化为有向图求解。显然，在这个有向图中，每个强连通分量里的奶牛都互相喜欢。那么，我们可以对其进行缩点操作。

显然，如果存在明星奶牛，一定存在一个强连通分量，使得该强连通分量缩点后的节点出度为 $0$ 。明星奶牛的个数也就是该强连通分量中的节点数量。

需要注意的是，在缩点后的图中，若存在 $\geq 2$ 个满足上述条件的强连通分量，那么这个图中不存在任何一个明星奶牛，因为无法满足所有其他的奶牛都喜欢该强连通分量中的奶牛。

代码实现：

```cpp
//  P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

#include<bits/stdc++.h>

using namespace std;
const int N = 1e4 + 10, M = 5e4 + 10;

int n, m;

class Graph {
private:
    vector<int> G[N];

public:
    int outDegree[N];

    void addEdge(int u, int v) {
        this->G[u].push_back(v);
        this->outDegree[u]++;
    }

    vector<int> operator[] (int idx) {
        return this->G[idx];
    }
} G1, G2;

int low[N], dfn[N], color[N], idx = 0, sccCnt = 0;
stack<int> s;
set<int> scc[N];

void tarjan(int u, Graph& G) {
    low[u] = dfn[u] = ++idx;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v, G);
            low[u] = min(low[u], low[v]);
        } else if (!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            color[x] = sccCnt;
            scc[sccCnt].insert(x);
            if (x == u) break;
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G1.addEdge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, G1);
    }
    for (int u = 1; u <= n; u++) {
        for (auto v : G1[u]) {
            if (color[u] != color[v]) {
                G2.addEdge(color[u], color[v]);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= sccCnt; i++) {
        if (G2.outDegree[i] == 0) {
            if (!ans) ans = scc[i].size();
            else {
                printf("0\n");
                return 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
```



浅谈 Tarjan


## 前言

作为第一次参加这样一个具有广泛辨识性的国际大赛的 OIer ，内心还是相当激动的，故写下这篇游记来记录一下。

笔者初二，作为打星队与其他两个队员一起去参加了 ICPC 区域赛西安站的比赛。赛区选址在西北工业大学长安校区，离西安市区远的不是一星半点，坐车需要一个半小时。

这次队友是：

- 李子晨（六年级）
- 张嘉宁（初一）

没想到我是最大的。。

## 5.13 星期六

从机场坐飞机到西安，大概两个小时就到了。本身打算订火车的，但是下午还有 NOC 的比赛，怕来不及就改了机票。下午 1:00 左右下了飞机，出机场就已经快 2:00 了，准备打车去学校附近的酒店。

下午 3:00 办完入住之后在附近吃了点面，3:30 回酒店打 NOC 的复赛。

NOC 的复赛倒不是很难，1.5h 打满 AK 了，就当是 ICPC 的热身吧。

晚上跟队友去签了到，逛了逛西工大，校园还是挺好看的。

![icpc-1](https://www.samzhangjy.com/assets/posts/icpc/icpc-1.jpeg)

![icpc-2](https://www.samzhangjy.com/assets/posts/icpc/icpc-2.jpeg)

![icpc-3](https://www.samzhangjy.com/assets/posts/icpc/icpc-3.jpeg)

![icpc-4](https://www.samzhangjy.com/assets/posts/icpc/icpc-4.jpeg)

![icpc-5](https://www.samzhangjy.com/assets/posts/icpc/icpc-5.jpeg)

![icpc-6](https://www.samzhangjy.com/assets/posts/icpc/icpc-6.jpeg)

![icpc-7](https://www.samzhangjy.com/assets/posts/icpc/icpc-7.jpeg)

![icpc-8](https://www.samzhangjy.com/assets/posts/icpc/icpc-8.jpeg)

![icpc-9](https://www.samzhangjy.com/assets/posts/icpc/icpc-9.jpeg)

![icpc-10](https://www.samzhangjy.com/assets/posts/icpc/icpc-10.jpeg)

## 5.14 星期日

正式比赛。

早上 7:00 起的，吃了个肉夹馍 9:00 去参加的热身赛。

热身赛没咋好好打，主要就是熟悉了一下 CodeBlocks 该怎么用，顺带培训了一下队友 Ubuntu 的使用方法。

9:30 热身赛结束之后想去看开幕式发现楼下已经坐满了，遂在三楼机房附近围着看了一下。

![icpc-11](https://www.samzhangjy.com/assets/posts/icpc/icpc-11.jpeg)

10:00 正式开赛，我们题还没从袋子里拿出来一刷榜发现已经有人把签到题秒了，遂开了 G 题。

G 题一眼发现性质，答案永远是 $1 \sim n$ 的数列，循环输出就行。于是乎我就打了一个 `for` 循环交上去过了，用时大概 5 min 。

后来发现别的题其他队也没有成功的提交，于是三个人开了三个题，我开 J 题，zjn 开了 I 题，lzc 开了 E 题。

J 题我研究一段时间之后发现没有太多思路，正好 lzc E 题也卡住了就去和他交流一下 J 题。

讨论的过程中我发现可以用类似倍增的方法进行求解，和 lzc 确定了大致思路之后敲了一下代码过掉了 J 题。这里有一个有戏剧性的小插曲就是这份代码由于精度问题甚至没有过第三个 `1 0` 的样例。。但是估计评测的时候有 SPJ ，我们又把精度调高了所以给过了。

这时候已经快 12:00 了，我们刚刚过 2 题。

在此期间 zjn 一直在搞 I 题，发现了一个操作 $2$ 的规律：$\text{round}(\sqrt{2x} + 1)$ 有类似 $[2, 3, 3, 4, 4, 4]$ 的性质，又鼓捣了一下敲了两个二分发现答案一直不对。最后 debug 了半天交了好几发终于过了 I 题。神奇的是这道题在我们过的时候只有 4 个队 A 了，环顾四周发现几乎没有人有 I 题的棕色气球。

此时差不多 12:50 ，过了 3 题，但是罚时由于之前 I 题交的太多很高。

zjn 搞 I 题的时候我和 lzc 在看当时很多队伍过掉了的 A 题。一开始以为是博弈题，一直没有研究明白，后来发现合法的序列是可以通过某些条件构造的，但是没有在限定复杂度内求解的思路。zjn 也来看了 A 题，仍然是没有头绪。最后快 14:00 的时候 lzc 搞了一个我高攀不起的逆元过掉了 A。

在这之前我们暂时放弃了 A ，我开始开 E 题，lzc 开 H 题。E 题一开始脑子一热以为是二维前缀和，写完代码才发现样例都过不去，之后也没有想出来很好的处理方式，摆了。lzc 的 H 题好像发现了一个重要的性质，20 多行的代码就过了 H 题，我和 zjn 直呼牛逼。

最后一个小时 zjn 在用 DP 搞 E 题，我和 lzc 开 D 题。最后 E 题没搞出来，D 题倒是有一个复杂度在边缘的 $O(n^2m)$ 的解法，但是实现的时候只有 20 min ，有个奇怪的 bug 没有找出来，300 分钟的时候交了一发错解 WA 了，比赛结束。

奇怪的是最后竟然过了五题，排名88 ，拿了银牌。神奇的是最后因为失误给我们发了牌子，但是问了一下之后照完相就还给人家了。

![icpc-12](https://www.samzhangjy.com/assets/posts/icpc/icpc-12.jpg)

![icpc-13](https://www.samzhangjy.com/assets/posts/icpc/icpc-13.jpg)

![icpc-14](https://www.samzhangjy.com/assets/posts/icpc/icpc-14.jpeg)

~~总的来说，这场比赛全靠 lzc A 的 3 道题和 zjn 的 I 题~~

ICPC 2023 西安站游记

CSP-J 2022 题解


## 题目描述

### 说明

wjr 最近学习了《树》的概念

他觉得很有趣，于是自己花了一棵包含 n*n* 个节点的树，每条边的边长不一定相同，并且自己指定了一个节点 $p$ 为根节点

为了让这棵树更加有趣，wjr 把每条边设置成了有向边，这条边只允许从父亲走向儿子

现在 wjr 想知道，这棵树上有多少路径长度为 $k$ 的简单路径？

### 输入格式

输入第一行包含三个整数 n,p,k*n*,*p*,*k*，如题意所示。

接下来 n-1*n*−1 行每行包含三个整数 u,v,x*u*,*v*,*x* ，表示节点 u*u* 和节点 v*v* 之间存在一条长度为 x*x* 的边。


对于 $20\%$ 的数据: $10 \leq n \leq 100$。

对于 $50\%$ 的数据: $10 \leq n \leq 3000$。

对于 $100\%$ 的数据: $10 \leq n \leq 200000;1 \leq p \leq n;1 \leq x \leq 10^5;1 \leq k \leq 10^5$。

### 输出格式

输出一行，该行包含一个整数，表示答案

### 样例

#### 输入数据 1

```input1
5 2 2
2 1 2
2 3 1
3 4 1
3 5 1
```

#### 输出数据 1

```output1
3
```

## 题解

昨天%你赛的题，暴力挂了拿了零分。看了题解之后发现好巧妙，于是诞生了这篇文章。

首先肯定这是一道裸的图论题，求树上权值和为 $k$ 的简单路径数目。题目规定每条边是有向边，但是后面能发现这是个巨坑。

首先既然是棵树，我们不难想到跟这道题有关的性质：

- 从根节点到树上任意一个点有且仅有一条唯一路径
- 树上不存在环
- 根节点一定能够到达任意一个节点

首先想到的是考虑枚举每个点从它的祖宗节点经过的每条路径（可能有重合）的权值和，但显然 $O(n^2)$ 的复杂度会超时。

~~考虑到上道题就是滑动窗口，~~考虑使用滑动窗口的方式进行优化。从树上每个叶子节点向上遍历直到根节点的路径是唯一的，所以可以使用树上滑动窗口解决。

具体操作就是找到一个叶子节点后，对从该节点到根节点的这条路径进行滑动窗口，在缩小左端点的同时尽可能缩小右端点。说的形象点就是像蛇一样在这条路径上伸缩，直到总和为 $k$ 或者到达根节点为止。

目前为止，一切看起来都还好，只需要实现树上滑动窗口即可。但是，仔细看题可以发现，给定的边并没有指定位置关系：$u$ 可以是 $v$ 的父亲，也可能是 $v$ 的孩子！例如下面这棵树：

![tree](/assets/posts/solution-root-tree/tree.png)

这时，如果配上这样的输入：

```5 1 3
5 4 1
3 4 2
1 3 1
2 1 3
```

我们的算法就会出现错误的结果。解决方案也很简单，建立双向边即可。这就是这道题最大的坑点，也是最巧妙的点。建立双向边之后我们只需要判断是否走重即可。

## 代码

```cpp
#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 2 * 1e5 + 10;

struct Node {
    int id, w, p;

    Node() {}

    Node(int _id, int _w, int _p) { this->id = _id, this->w = _w; this->p = _p; }
};

queue<Node> q;
int h[N], vtx[2 * N], nxt[2 * N], w[2 * N], idx, vis[2 * N];
int n, p, k, ans, maxEdge, fa[2 * N], sum[2 * N];

void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int prev, int cur) {
    fa[cur] = prev;
    int p = h[cur];
    bool isLeaf = true;
    while (p != -1) {
        if (prev == vtx[p]) {
            p = nxt[p];
            continue;
        }
        isLeaf = false;
        sum[vtx[p]] = sum[cur] + w[p];
        dfs(cur, vtx[p]);
        p = nxt[p];
    }
    if (isLeaf) {
        int l = cur, r = cur;
        while (r != p) {
            if (vis[l] || sum[l] < k) break;
            vis[l] = 1;
            while (sum[l] - sum[r] < k) r = fa[r];
            if (sum[l] - sum[r] == k) ans++;
            l = fa[l];
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> p >> k;
    for (int i = 1; i <= n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dfs(-1, p);
    cout << ans << endl;
    return 0;
}
```

AC++!

wjr的有根树 题解


## 什么是树状数组？

**树状数组**， 或 Binary Indexed Tree（也称 **Fenwick Tree** ），是一种能够高效更新并计算数列前缀和的数据结构。

树状数组的实现主要基于计算二进制 lowbit（也就是值为 $1$ 的最低位）。

## 原理

既然树状数组与线段树类似，我们不妨将线段树的实现方式先搬过来看看。对于一个表示数列 $a_i$ 的线段树 $S$ ，线段树会通过数列 $a$ 递归建树，使用类似归并的思想维护节点。一开始，线段树为空，然后从根节点开始分枝，再进行递归展开，如此往复，直到叶子结点为止。

也就是说，在线段树中每一个非叶子结点都管理着当前孩子结点的信息。这种操作的具体实现就是 `pushup` 操作。这样在查询时，我们只需要找到对应的父亲节点即可。

而树状数组所使用的策略与线段树几乎别无二致：同样适用父亲节点来表示其孩子节点的信息，且同为递归定义。同样地，在查询时只需要查询所属叶子结点的父亲节点即可。显然，对于根节点将会管理数列中的所有节点的信息。

![fenwick-1](https://blog.samzhangjy.com/assets/posts/fenwick-tree/fenwick-1.png)

上图就是一个典型的使用树状数组维护出来的树形结构。最上方的 `a[]` 表示数据数组，一一对于最下方的叶子结点（圆圈）。每一个父亲节点都使用方形表示，控制着至少两个结点。

将上图中的结点进行编号，得：

![fenwick-2](https://blog.samzhangjy.com/assets/posts/fenwick-tree/fenwick-2.png)

每个节点右面的蓝色数字为当前节点的编号。如果将树状数组表达为 $b_i$ ，原始数组为 $a_i$ ，则有：
$$
b_1 = a_1\\
b_2 = a_1 + a_2\\
b_3 = a_1 + a_2 + a_3\\
b_4 = a_4\\
b_5 = a_4 + a_5\\
b_6 = a_4 + a_5 + a_6
$$
如果把下标都转换成二进制，则有：
$$
b_{(1)_2} = a_{(1)_2}\\
b_{(10)_2} = a_{(1)_2} + a_{(10)_2}\\
b_{(11)_2} = a_{(1)_2} + a_{(10)_2} + a_{(11)_2}\\
b_{(100)_2} = a_{(100)_2}\\
b_{(101)_2} = a_{(100)_2} + a_{(101)_2}\\
b_{(110)_2} = a_{(100)_2} + a_{(101)_2} + a_{(110)_2}
$$
不难发现其中的规律：
$$
b_i = a_{i - 2^k + 1} + a_{i - 2^k + 2} + \cdots + a_i
$$
其中 $k$ 为 $i$ 的二进制表示下 $1$ 的最低位的位置。例如 $i = (8)_{10} = (1000)_2$ 时，$k = 3,\ b_8 = a_1 + a_2 + \cdots +a_8$ 。

考虑计算下述表达式：
$$
s_i= \sum_{j=1}^{i} a_j
$$
根据 (3) 式易得：
$$
s_i = b_i + b_{i - 2^{k_1}} + b_{i - 2^{k_1} - 2^{k_2}} + \cdots
$$
其中 $k_j$ 表示当前第 $j$ 次访问时，从 $i$ 一直循环对最低位上的 $1$ 取反后当前 $i$ 的值的 $1$ 的最低位。例如，对于计算 $s_4$ ，我们有：
$$
s_4 = b_4 + b_{4 - 2^0} = b_4 + b_3 = a_4 + a_1 + a_2 + a_3 = 25
$$
其中 $k$ 的二进制变化过程为：
$$
k = (4)_{10} = (100)_2 \rarr k = (100)_2 - (100)_2 = (0)_2 \rarr \text{End.}
$$
这样我们就完成了前缀求和操作。

对于修改操作，我们也可以采用类似的思想。修改操作无非就是将给定的增加值依次向上更新传递。例如，将 $a_5$ 增加 $3$ 我们需要依次向上更新 $b_5$ 与 $b_6$ 。这样的变化过程在求和操作时已经说明，只需要进行反向操作即可。

对于 $a_5 = a_{(101)_2}$  ，我们需要更新其所有祖宗节点，即所有包括 $a_5$ 值的 $b_i$ 。我们不妨从 $i = (5)_{10} = (101)_2$ 进行操作。注意到 $a_5$ 的父亲节点包括 $\{b_5, b_6\} = \{b_{(101)_2}, b_{(110)_2}\}$ 。所以可以将 $i$ 每次增加 $2^k$ ，其中 $k$ 为 $i$ 的二进制表示下 $1$ 的最低位的位置。$i = 5$ 时 $k$ 的变化过程如下：
$$
i = 5 = (101)_2,\ k = 0 \rarr i = i + 2^k = 5 + 1 = 6,\ k = 1 \rarr \text{End.}
$$
这样我们就可以进行单点修改操作。

## 实现

注意到上述所有操作都依赖于一个重要操作：求某数 $x$ 的二进制下最低 $1$ 的位置 $k$。这时不妨引出一个简单的函数 `lowbit` ：

```cpp
int lowbit(int x) {
  return x & -x;
}
```

该函数的返回值即为 $2^k$ ，而树状数组所需操作也仅仅是 $2^k$ 的值。该函数原理如下：

1. 若 $x = (17)_{10}$ ，则其补码为 $(010001)_补$ ，$(-x)_补$ = $(101111)_补$ 。
2. 计算 `x & -x` ，结果为 $(000001)_2 = (1)_{10}$ 。
3. 验证上述操作，$x$ 的二进制最低 $1$ 的位置从零开始计数为 $0$ ，$2^k = 2^0 = 1$ ，结果正确。

于是我们便不难写出模板代码：

```cpp
template <typename T = int>
class FenwickTree {
   private:
    T tr[N];

    int lowbit(int x) { return x & -x; }

   public:
    void add(int x, T k) {
        while (x <= N) {
            tr[x] += k;
            x += lowbit(x);
        }
    }

    T prefix_sum(int x) {
        T ans = 0;
        while (x >= 1) {
            ans += tr[x];
            x -= lowbit(x);
        }
        return ans;
    }
  
    T sum(int l, int r) {
      return prefix_sum(r) - prefix_sum(l - 1);
    }
};
```

不难发现虽然基本操作是前缀和，但仍然可以使用两个前缀和的差求出任意区间和。值得注意的是，虽然 `lowbit` 函数仅支持整数操作，但树状数组支持任意数据类型：`lowbit` 维护的是数组下标，并不对实际内容进行操作。

不难发现求和与修改操作都是 $O(\log n)$ 的：每次操作的最坏情况即为从叶子结点更新至根节点，也就是需要遍历 $h = \text{树高}$ 次。而树状数组又是完全二叉树，所以 $h \leq \log_2(n)$ 。

对比线段树，我们发现树状数组并不能很高效地处理区间更新问题。注意到原本的前缀和操作，我们不妨将其改为差分操作。这样，每次存储 $b_i$ 则为 $a$ 的差分数组，即 $b_i = d_i + d_{i - 1} + \cdots + d_1$ ，其中 $d_i$ 表示 $a$ 的差分数组，即 $d_i = a_i - a_{i - 1}$ 。

这样，对于修改操作我们只需要对 $b_l$ 增加 $x$ ，$b_r$ 减少 $x$ 即可。当前这样的坏处就是无法进行区间查询操作：对差分数组进行求和相对原数组而言已经失去意义。但是，我们仍可以通过差分数组的特性来查询某一节点的值：对前 $i$ 个差分数组元素进行求和即为原数组的第 $i$ 个元素的值。

尽管无法直接进行区间求和的维护操作，我们仍可以通过维护两个树状数组的方式同时进行区间修改与区间查询的操作。参考 [OI-Wiki](https://oi-wiki.org/ds/fenwick/#%E5%8C%BA%E9%97%B4%E5%8A%A0--%E5%8C%BA%E9%97%B4%E6%B1%82%E5%92%8C) 。但是本人认为进行这样的操作不如使用线段树方便。

例题：<https://www.luogu.com.cn/problem/P3368> 。

显然对于这道题，我们需要进行区间修改与单点查询。参考代码如下：

```cpp
// Problem: P3368 【模板】树状数组 2
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3368
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e5 + 10;

int bit[N], n, m, x, y, k, op, a[N];

int lowbit(int x) { return x & -x; }

void add(int x, int k) {
    while (x <= n) {
        bit[x] += k;
        x += lowbit(x);
    }
}

int prefix_sum(int x) {
    int ans = 0;
    while (x >= 1) {
        ans += bit[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        add(i, a[i] - a[i - 1]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        } else {
            cin >> x;
            cout << prefix_sum(x) << endl;
        }
    }
    return 0;
}
```

注意到核心模板代码无需改变。

## 总结

不难发现，朴素树状数组可以进行大部分线段树可以进行的操作：区间求和与单点更新、区间修改与单点查询。但是，这两组操作却无法使用一个树状数组同时实现。简单来说，树状数组能做的操作线段树也一定能做，但反之却不亦然。

在对于高级操作没有要求的题目下，使用树状数组是一个很好的选择，因为其代码复杂度明显较低。但在复杂的题目时，线段树会略胜一筹。

值得注意的是，虽然线段树与树状数组时间复杂度相同，但树状数组常数略小。在更新操作时，树状数组不一定一定要遍历 $\log n$ 个节点，而线段树却必须遍历所有 $\log n$ 个节点。但是该常数复杂度可以忽略，二者时间消耗均等。但是树状数组在空间消耗上要明显低于线段树：线段树通常需要 $4$ 倍的数组空间，而树状数组仅需要 $1$ 倍。

总之，哪个好用用哪个。

浅谈树状数组


## 什么是堆？

堆是一种特殊的树，其每个节点都有一个权重 $w_i$ ，且每个节点的权重 $w_i$ 均小于/大于其父亲节点。

![heap-1](https://tva1.sinaimg.cn/large/e6c9d24ely1h57n9ki8lhj207w08j3yj.jpg)

上图就是一个典型的堆。如果每个节点的权重都 $\geq$ 其父亲节点的权重，那么这个堆就是一个小根堆，反之则是大根堆。不难发现，上图是一个小根堆。

我们今天所要讨论的二叉堆则是一个用数组维护的完全二叉树，也适用于上述规则。

C++ STL 中的 `priority_queue` 就是一个典型的堆。

## 堆的操作

### 插入

给定一个合法的堆 $H$ ，现在需要插入一个权值为 $x$ 的元素到 $H$ 中，这就是插入操作。还是上面的那棵树，现在我们希望加入一个元素 $5$ 到堆里：

![heap-2](https://blog.samzhangjy.com/assets/posts/heap/heap-2.png)

下方的数组表示当前堆的存储情况。很显然我们可以先随便把这个节点加到堆里，然后再想办法维护整个堆使其合法。那么我们将新节点先挂载到节点 6 的位置（数组下标），然后考虑如何进行维护。

显然对于当前节点无非就有两种情况：

1. 当前节点小于父亲节点，需要向上移动；
2. 当前节点大于等于父亲节点，无需移动。

那么我们就可以一直向上移动新节点直到满足情况 (2) 时为止。

![heap-3](https://blog.samzhangjy.com/assets/posts/heap/heap-3.gif)

对于这个堆，我们只需要将新节点向上移动一层即可。这个操作就叫做 **向上调整** ，或 **Decrease Key** ，代码如下：

```cpp
// 向上调整操作，x 为需要进行调整位置的元素下标
void up(int x) {
  while (x > 1 && H[x] < H[x / 2]) {
    // 遇到不合法的就交换父亲节点与当前节点
    swap(H[x], H[x / 2]);
    x /= 2;
  }
}

// 插入操作，x 为需要插入的值
void insert(int x) {
  n++;
  H[n] = x;
  up(n);
}
```

该算法的时间复杂度为 $O(\log n)$ ，其中 $n$ 为节点数。证明显而易见，`up()` 函数中的 `while` 循环最多执行 $k$ 次，其中 $k$ 为堆的高度。显然，$k = \log n$ 。

### 删除

删除操作将会删除当前堆的根节点，在我们的堆中也就是最小的元素。很明显我们没办法直接删除根节点，因为那样会导致整个堆变成两个堆。我们不妨考虑将根节点与最后一个节点互换，然后再像插入操作那样想方设法维护这个堆使其满足性质。

很明显交换、删除根节点后的堆可能不满足我们小根堆的性质，也就是根节点可能比孩子节点还要大。那么我们就可以按照向上调整的思路，写出 **向下调整** ，来维护我们的堆。

对于向下调整，我们从当前节点的子节点中找到一个最小的元素互换，一直重复此操作到最下层。

![heap-4](https://blog.samzhangjy.com/assets/posts/heap/heap-4.gif)

参考代码：

```cpp
// 向下调整操作，x 为需要调整的下标
void down(int x) {
  while (x * 2 <= n) {
    int cur = x * 2;
    if (cur + 1 <= n && H[cur + 1] < H[cur]) cur++;
    // 当前子树根节点符合条件意味着子树的子树也符合条件了
    if (H[cur] <= H[x]) break;
    swap(H[cur], H[x]);
    x = cur;
  }
}

// 删除根节点操作，返回原根节点的值
int remove() {
  int ret = H[1];
  H[1] = H[n], n--;
  down(1);
}
```

删除操作的时间复杂度同样为 $O(\log n)$ ，其中 $n$ 为元素个数。证明同插入操作。

### 查询

查询操作能够查找当前堆内的最小（或最大，依据大小根）元素。这可能是所有二叉堆操作中最没有脑子的一个了……直接返回根节点即可。代码如下：

```cpp
// 查询操作，返回当前堆内最小值（根节点）
int query() {
  return H[1];
}
```

显然时间复杂度为 $O(1)$ 。

### 建堆

基本的增删改查操作有了，接下来就是如何从一个一直序列中转化为堆了。很显然我们可以从空堆开始逐个进行 `insert` 操作，时间复杂度为 $O(n \log n)$ 。那么，有没有时间复杂度更优的算法呢？

答案是肯定的。如果我们用逆向思维思考整个问题，从最底层的叶子节点开始，进行向下调整的操作，使得当前每个子节点的子树都满足堆的条件。这样，我们变相地合并了两个子堆，从而达到了我们想要的结果。

参考代码如下：

```cpp
// 建堆操作，a[] 为原始序列，n 为序列长度
void build(int a[], int n) {
  for (int i = 1; i <= n; i++) H[i] = a[i];
  for (int i = n; i >= 1; i--) down(i);
}
```

该算法的时间复杂度为 $O(n)$ ，关于时间复杂度的证明可以参见 [OI-Wiki](https://oi-wiki.org/ds/binary-heap/#%E6%96%B9%E6%B3%95%E4%BA%8C%E4%BD%BF%E7%94%A8%E5%90%91%E4%B8%8B%E8%B0%83%E6%95%B4) 或《算法导论》6.3 节。

### 模板题

链接：[洛谷 P3378 堆](https://www.luogu.com.cn/problem/P3378) 。

题目要求增删查三种操作，妥妥的模板。下面给出面向对象版的代码：

```cpp
// Problem: P3378 【模板】堆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3378
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 1e6 + 10;

int n, op, x;

template <typename T, int N = int(1e6 + 10), typename U = less<int>>
class Heap {
   private:
    int size;
    T H[N];
    U cmp = U();

   public:
    Heap() { size = 0; }

    void up(int x) {
        while (x > 1 && cmp(H[x], H[x / 2])) {
            swap(H[x], H[x / 2]);
            x /= 2;
        }
    }

    void insert(int x) {
        size++;
        H[size] = x;
        up(size);
    }

    void down(int x) {
        while (x * 2 <= size) {
            int cur = x * 2;
            if (cur + 1 <= size && cmp(H[cur + 1], H[cur])) cur++;
            if (cmp(H[x], H[cur])) break;
            swap(H[cur], H[x]);
            x = cur;
        }
    }

    int remove() {
        int ret = H[1];
        H[1] = H[size], size--;
        down(1);
        return ret;
    }

    int query() { return H[1]; }

    bool empty() { return size <= 0; }
};

Heap<int> H;

int main() {
    cin >> n;
    while (n--) {
        cin >> op;
        if (op == 1) {
            cin >> x;
            H.insert(x);
        } else if (op == 2) {
            if (H.empty()) continue;
            cout << H.query() << endl;
        } else {
            if (H.empty()) continue;
            H.remove();
        }
    }
    return 0;
}
```

## 对顶堆

对顶堆，顾名思义，是一种由一对大小根堆结合而成的数据结构，可用于**动态维护序列的第 $k$ 大值**，例如动态维护序列中位数等。

*【详情待补充】*

浅谈堆


看到各位大佬都是用的 Floyd ，让本蒟蒻来~~水~~一篇 SPFA 吧（）

## Description

给定一个边权均为 $1$ 的有向无环图，求该图的最长路。

## Solution

看到题第一反应是这题好难，但其实不然。所谓“最长路”只不过就是把边权都换成负数在新图上面跑一遍最短路而已。

于是，我们就可以开开心心地敲上 SPFA 板子然后取最值啦！

## Code

```cpp
// Problem: UVA10000 Longest Paths
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA10000
// Memory Limit: 0 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5010, INF = 0x3f3f3f3f;

int n, T = 1, u, v, ans, minn, s;
int h[N], w[N], vtx[N], nxt[N], idx;
long long dis[N], vis[N];
queue<int> q;

// 邻接表存图
void addEdge(int a, int b, int c) {
    vtx[idx] = b, nxt[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// SPFA 板子
void spfa(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty()) {
        int tmp = q.front();
        vis[tmp] = 0;
        int p = h[tmp];
        while (p != -1) {
            int v = vtx[p];
            if (dis[tmp] + w[p] <= dis[v]) {
                dis[v] = dis[tmp] + w[p];
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
            p = nxt[p];
        }
        q.pop();
    }
}

int main() {
    while (cin >> n) {
        // 输入到0结束
        if (n == 0) break;

        // 初！始！化！
        memset(h, -1, sizeof(h));
        memset(vtx, 0, sizeof(vtx));
        memset(nxt, 0, sizeof(nxt));
        memset(w, 0, sizeof(w));
        idx = 0;

        cin >> s;
        // 存边
        while (cin >> u >> v) {
            if (u == 0 && v == 0) break;
            // 存的是负边权
            addEdge(u, v, -1);
        }

        spfa(s);
        ans = -1, minn = INF;
        for (int i = 1; i <= n; i++) {
            if (dis[i] < minn) {
                ans = i, minn = dis[i];
            }
        }
        cout << "Case " << T << ": The longest path from " << s
             << " has length " << -minn << ", finishing at " << ans << "."
             << endl
             << endl;
        T++;
    }
    return 0;
}
```

## 附：为什么不能用 Dijkstra 求最长路

Dijkstra 使用贪心算法来计算最短路，依赖于最优子结构求解。与存在负边权的图同理，使用 Dijkstra 求最长路不满足最优子结构的条件：选择当前最长的边不一定代表总体最长。

在任意图上求最长路[被证明是 NP-Hard 的](https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs) ，但如果在类似此题中的 DAG（有向无环图）中最长路却可以使用这篇题解中的 SPFA 之类的算法求解。

**参考：**

- <https://en.wikipedia.org/wiki/Longest_path_problem>
- <https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag>
- <https://blog.csdn.net/hesorchen/article/details/115370721>

如果题解中有错误还请大佬指出qwq

[图论] UVA10000 Longest Paths 题解


## 什么是 ST 表

ST 表，即 Sparse Table ，是一种基于倍增思想的数据结构，常用来解决静态 RMQ（**R**ange **M**inimum / **M**aximum **Q**uery，区间最值询问）问题。

一般来讲，ST 表可用于解决大部分区间可重复贡献问题。此处的**可重复贡献问题**指，对于任意的运算 $\text{opt}$ ，满足 $x\ \text{opt}\ x = x$ 的即为可重复贡献问题，例如对于最值问题有 $\max(x,x) = x$。[^1]

## 浅析 ST 表

ST 表的基本思路基于可重复贡献问题的特性，即两个重叠子问题的重复计算不会影响最终的计算答案。下面是一道 ST 表的模板题：

给定 $N$ 个数字与 $M$ 次询问，求对于任意询问 $i$ ，区间 $[l_i, r_i]$ 内的最大值。

详见 [洛谷 P3865](https://www.luogu.com.cn/problem/P3865) 。

对于这个问题，不难想到暴力的解法：对于每个询问查询最大值，但是在 $M \leq 2 \times 10^6$ 的数据范围下很明显会超时。于是我们考虑倍增的思路：用 $f(i,j)$ 表示第 $i$ 个数往后 $2^j - 1$ 个数的最大值，即区间 $[i, i + 2^j - 1]$ 的最大值。

于是，有了这样的定义，我们不难发现 $f(i,j)$ 的值取决于 $[i, i + 2^{j - 1} - 1]$ 与 $[i + 2^{j - 1}, i + 2^j - 1]$ 的值，如此往复，在实现过程中的时间复杂度约为 $O(N \times \log N)$ 。

构建部分代码如下：

```cpp
void build() {
    int lim = log2(n);
    for (int j = 1; j <= lim; j++) {
        // i + (1 << j) - 1 为当前区间右端点
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            // 当前值取决于左右两子区间的值
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}
```

接下来是询问操作。对于任意区间 $[l,r]$ ，我们一定能够找到两个区间 $A,B$ ，使得 $A$ 与 $B$ 的并集完全覆盖 $[l,r]$ ，$A$ 与 $B$ 之间可以有重合部分。如果设 $A$ 为左子区间，$B$ 为右子区间，不难发现 $A = [l, l + 2^k - 1]$ ，其中 $k = \log_{2}(r - l + 1)$ 。

对于区间 $B$ ，假设需要找到的左端点为 $x$ ，即 $B = [x, r]$ 。显然需要使得 $x + 2^k - 1 = r$ ，移项，得 $x = r - 2^k + 1$ 。所以区间 $B = [r - 2^k + 1, r]$ 。这样，$A + B$ 的覆盖范围一定包含 $[l, r]$ 中的任意元素，取 $\max(A, B)$ 即为答案。

ST 表的查询操作拥有优秀的 $O(1)$ 时间复杂度，每次仅需进行一次 $\log$ 操作与取最值操作。但取对数的步骤显然可以使用预处理进行优化。查询部分代码如下：

```cpp
int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
```

基于这样的实现方式，ST 表可以做到 $O(n \log n)$ 的预处理与 $O(1)$ 询问，但是不支持修改操作。完整版代码如下：

```cpp
// Problem: P3865 【模板】ST 表
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3865
// Memory Limit: 125 MB
// Time Limit: 800 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 1e5 + 10, M = 20;

int n, m, a[N], f[N][M];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

void build() {
    int lim = log2(n);
    for (int j = 1; j <= lim; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    // 数据过大需要优化输入输出
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        f[i][0] = a[i];
    }
    build();
    for (int i = 1; i <= m; i++) {
        int l = read(), r = read();
        printf("%d\n", query(l, r));
    }
    return 0;
}
```

## 习题

### P2880 [USACO07JAN] Balanced Lineup G

链接：<https://www.luogu.com.cn/problem/P2880> 。

#### 题目大意

给定 $N$ 个整数以及 $M$ 个询问，求对于每个询问 $i$ ，区间 $[l_i, r_i]$ 的最大值与最小值之差。

#### 分析

几乎是 RMQ 模板题，需要支持两种最值操作，数据范围甚至没有模板题严格，使用朴素 ST 表即可。

#### 代码

```cpp
// Problem: P2880 [USACO07JAN] Balanced Lineup G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2880
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 5 * 1e4 + 10, M = 16;

int n, m, a[N];

template <typename T, typename U = less<int>>
class SparseTable {
   private:
    T f[N][M];
    int len;
    U cmp;

   public:
    SparseTable(int _len, int data[]) {
        len = _len;
        cmp = U();
        for (int i = 1; i <= _len; i++) {
            f[i][0] = data[i];
        }
        build();
    }

    void build() {
        int lim = log2(len), a = -1, b = -1;
        for (int j = 1; j <= lim; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                a = f[i][j - 1], b = f[i + (1 << (j - 1))][j - 1];
                f[i][j] = cmp(a, b) ? a : b;
            }
        }
    }

    int query(int l, int r) {
        int k = log2(r - l + 1);
        int a = f[l][k], b = f[r - (1 << k) + 1][k];
        return cmp(a, b) ? a : b;
    }
};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    SparseTable<int, less<int>> minTable(n, a);
    SparseTable<int, greater<int>> maxTable(n, a);

    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        cout << maxTable.query(l, r) - minTable.query(l, r) << endl;
    }
    return 0;
}
```

更多习题补充中……

[^1]: 参见 [OI-Wiki](https://oi-wiki.org/ds/sparse-table/#_1) 。

浅谈 ST 表


## 题目

链接：<https://www.luogu.com.cn/problem/P1077>

### 题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 $m$ 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 $n$ 种花，从 $1$ 到 $n$ 标号。为了在门口展出更多种花，规定第 $i$ 种花不能超过 $a_i$ 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

### 输入格式

第一行包含两个正整数 $n$ 和 $m$，中间用一个空格隔开。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，依次表示 $a_1,a_2, \cdots ,a_n$。

### 输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 $10^6+7$ 取模的结果。

### 样例 #1

#### 样例输入 #1

```
2 4
3 2
```

#### 样例输出 #1

```
2
```

### 提示

【数据范围】

对于 $20\%$ 数据，有 $0<n \le 8,0<m \le 8,0 \le a_i \le 8$。

对于 $50\%$ 数据，有 $0<n \le 20,0<m \le 20,0 \le a_i \le 20$。

对于 $100\%$ 数据，有 $0<n \le 100,0<m \le 100,0 \le a_i \le 100$。

NOIP 2012 普及组 第三题

## 题解

### 分析

第一眼看到以为是暴力 DFS ，看了一下数据范围发现自己错了（虽然记忆化好像也能做），于是容易想到动态规划的解法。

那么接下来就要考虑如何进行状态转移了。设 $dp_{i,j}$ 表示当前选了前 $i$ 种花，总计 $j$  盆。不难想到下述转移方程：
$$
dp_{i,j} = \sum_{k = 0}^{a_i} dp_{i - 1, j - k} \mod{p}
$$
其中 $k$ 表示第 $i$ 种花选多少个，那么答案显而易见，求和即可。

这道题其实还可以用滚动数组降维（毕竟只依赖 $i-1$ 的状态），甚至还有大佬直接降维，本蒟蒻 ~~太懒~~ 就不搞了。

### 代码

```cpp
// Problem: P1077 [NOIP2012 普及组] 摆花
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1077
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 110, MOD = 1e6 + 7;

int n, m, a[N], dp[N][N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 初始化，0盆花只有一种方案（不摆）
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= a[i]; k++) {
                if (k > j) break;  // 大于能选的就退出
                dp[i][j] += dp[i - 1][j - k], dp[i][j] %= MOD;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}
```

AC++！

[DP] P1077 [NOIP2012 普及组] 摆花 题解


## 题目

链接：<https://www.luogu.com.cn/problem/P1522>

### 题目描述

Farmer John 的农场里有很多 **牧区**。有的路径连接一些特定的牧区。**一片所有连通的牧区** 称为一个 **牧场**。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John 就有 **多个** 牧场了。

John 想在牧场里添加 **恰好** 一条路径。对这条路径有以下限制：

一个牧场的 **直径** 就是牧场中 **最远** 的两个牧区的距离（本题中所提到的所有距离指的都是 **最短的距离**）。考虑如下的有 5 个牧区的牧场，牧区用 `*` 表示，路径用直线表示。每一个牧区都有自己的坐标：

```plain
                (15,15) (20,15)
                 D       E
                 *-------*
                 |     _/|
                 |   _/  |
                 | _/    |
                 |/      |
        *--------*-------*
        A        B       C
     (10,10)  (15,10) (20,10)
```
这个牧场的直径大约是 $12.07106$，最远的两个牧区是 A 和 E，它们之间的最短路径是 $A \to B \to E$。

这里是 John 的另一个牧场：

```plain
                         *F(30,15)
                        / 
                      _/  
                    _/    
                   /      
                  *------* 
                  G      H
                  (25,10)   (30,10)
```

在这个例子中，他刚好有这两个牧场。John 将会在这两个牧场中各选一个牧区（即从 $\{A,B,C,D,E\}$ 中选择一个牧区，从 $\{F,G,H\}$ 中选择一个牧区），然后用一条路径将它们连起来，使得连通后这个新的更大的牧场的直径尽可能小。

注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：

```plain
　 A  B  C  D  E  F  G  H 
A  0  1  0  0  0  0  0  0
B  1  0  1  1  1  0  0  0
C  0  1  0  0  1  0  0  0
D  0  1  0  0  1  0  0  0
E  0  1  1  1  0  0  0  0
F  0  0  0  0  0  0  1  0
G  0  0  0  0  0  1  0  1
H  0  0  0  0  0  0  1  0
```

其他邻接表中可能直接使用行列而不使用字母来表示每一个牧区。输入数据中不包括牧区的名字。

输入文件 **至少** 包括两个不连通的牧区。

请编程找出一条连接属于两个 **不同牧场** 的牧区的路径，使得连上这条路径后，这个更大的新牧场的直径尽可能小。输出在所有合法的连接方案中，新牧场直径的最小值。

### 输入格式

第一行一个整数 $N$（$1 \leq N \leq 150$），表示牧区数。

接下来 $N$ 行，每行两个整数 $X,Y$（$0 \leq X ,Y \leq 10^5$），表示 $N$ 个牧区的坐标。注意每个牧区的坐标都是不一样的。

接下来 $N$ 行，每行 $N$ 个数字，代表邻接矩阵 $M$。第 $i$ 行第 $j$ 列的数字为 $1$，表示 $i$ 号牧区和 $j$ 号牧区之间存在一条道路直接相连；第 $i$ 行第 $j$ 列的数字为 $0$，表示 $i$ 号牧区和 $j$ 号牧区之间不存在直接相连的道路。

保证 $M_{i,j} = M_{j,i}$。

### 输出格式

只有一行，包括一个实数，表示所求直径。数字保留六位小数。

只需要打到小数点后六位即可，不要做任何特别的四舍五入处理。

### 样例 #1

#### 样例输入 #1

```
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
```

#### 样例输出 #1

```
22.071068
```

### 提示

样例对应题目描述中的情况。

最优解是连接 C 牧区和 G 牧区，连接后图上只有一个牧场。这个牧场的直径为 $A \to B \to C \to G \to F$，长度约为 $22.071068$。可以证明不存在更优的方案。

USACO 2.4

## 题解

### 分析

这道题，一个字 —— 绕。先解释一下这道题里各个关键词的意思吧：

- 牧区：一个点
- 牧场：由多个牧区组成的连通块
- 两个牧区之间的距离：两个牧区在图上所对应点点最短路
- 牧场的直径：设两个端点分别为 $i,j$ ，使得牧场 $i$ 和牧场 $j$ 之间的距离最大
- 答案：一条端点为 $i,j$ 的路径，使得新的连通块（牧场）的直径最小（也就是说，使这个连通块内两个最远点的最短距离最大）

那么问题就分成了四个子问题：

1. 通过给定的邻接矩阵求出不同的连通块
2. 求任意点 $i,j$ 之间的最短路
3. 求每个牧场的直径
4. 求从每个点出发所到达的最远距离

对于问题一，显然是一个染色问题，考虑使用并查集求解。

对于问题二，注意到点的数量 $N \leq 150$  ，使用复杂度为 $\Theta(n^3)$ 的 Floyd 求多源最短路完全可以满足需求，故采用 Floyd 求解。虽然可以使用 Dijkstra + 斐波那契堆优化至接近 $\Theta(n^2 \times \log n)$ ，但对于此题来说需求不大。

对于问题三、四，显然有了上述两个子问题的结果后不难实现，采用 $\Theta(n^2)$ 的朴素枚举即可。

需要注意的是，最终的答案需要分为三种情况考虑。设当前答案使用 $i \lrarr j$ 边连接连通块 $A,B$ ，则当前答案 $S$ 为：
$$
S = \max(D_{A}, D_{B}, L_{i} + L_{j} + |i,j|)
$$
其中，$D_x$ 表示连通块 $x$ 的直径；$L_x$ 表示从点 $x$ 出发所到达的最远距离，$|u,v|$ 表示边 $u \lrarr v$ 的边权（即长度）。

最后枚举 $i,j$ 求最优答案即可。

### 代码

```cpp
// Problem: P1522 [USACO2.4] 牛的旅行 Cow Tours
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1522
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <memory.h>

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <vector>
using namespace std;
const int N = 200, M = 1e5 + 10, INF = 0x7f7f7f7f;

int n, bin[N];
// max_to_go[i] 表示从i出发到达的最远距离，diameter[i] 表示连通块i的直径
double g[N][N], max_to_go[N], diameter[N], ans = INF;

struct Point {
    int x, y;
} p[N];

int Find(int x) {
    if (bin[x] == x) return x;
    return bin[x] = Find(bin[x]);
}

void Union(int u, int v) {
    int fu = Find(u), fv = Find(v);
    if (fu != fv) {
        bin[fu] = fv;
    }
}

double get_dis(Point a, Point b) {
    return sqrt(pow(a.x - b.x * 1.0, 2) + pow(a.y - b.y * 1.0, 2));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) bin[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char ch;
            cin >> ch;
            if (ch == '1' || i == j) {
                g[i][j] = get_dis(p[i], p[j]);
                Union(i, j);
            } else {
                g[i][j] = INF;
            }
        }
    }
    // Floyd 板子
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        int fi = Find(i);
        for (int j = 1; j <= n; j++) {
            if (Find(i) != Find(j)) continue;
            // 最远距离
            max_to_go[i] = max(max_to_go[i], g[i][j]);
        }
        // 当前连通块的最远距离就是连通块内所有点所能到达的最远距离的最大值
        diameter[fi] = max(diameter[fi], max_to_go[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (Find(i) == Find(j)) continue;
            // 求 i, j 所在连通块的最大直径
            double max_diameter = max(diameter[Find(i)], diameter[Find(j)]);
            // 求最优答案
            ans =
                min(ans, max(max_to_go[i] + max_to_go[j] + get_dis(p[i], p[j]),
                             max_diameter));
        }
    }
    // 六位精度！！
    cout << fixed << setprecision(6) << ans << endl;
    return 0;
}
```

[图论] P1522 [USACO2.4] 牛的旅行 Cow Tours 题解


## 题目

链接：<https://www.luogu.com.cn/problem/P5837>

### 题目描述

Farmer John 最近为了扩张他的牛奶产业帝国而收购了一个新的农场。这一新的农场通过一个管道网络与附近的小镇相连，FJ 想要找出其中最合适的一组管道，将其购买并用来将牛奶从农场输送到小镇。

这个管道网络可以用 $N$ 个接合点（管道的端点）来描述，将其编号为 $1 \ldots N$。接合点 $1$ 表示 FJ 的农场，接合点 $N$ 表示小镇。有 $M$ 条双向的管道，每条连接了两个接合点。使用第 $i$ 条管道需要 FJ 花费 $c_i$ 美元购入，可以支持每秒 $f_i$ 升牛奶的流量。

FJ 想要购买一条管道组成一条单一路径，路径的两端点分别为接合点 $1$ 和 $N$。这条路径的花费等于路径上所有管道的费用之和。路径上的流量等于路径上所有管道的最小流量（因为这是沿这条路径输送牛奶的瓶颈）。FJ 想要最大化路径流量与路径花费之比。保证存在从 $1$ 到 $N$之间的路径。

### 输入格式

输入的第一行包含 $N$ 和 $M$。以下 $M$ 行每行以四个整数描述一条管道：$a$ 和 $b$（管道连接的两个不同的接合点），$c$（管道的花费），以及 $f$（管道的流量）。花费和流量均为范围 $1 \ldots 1000$ 之内的正整数。

### 输出格式

输出 $10^6$ 乘以最优解的值，并向下取整（也就是说，如果这个数本身不是整数，输出小于它的最接近它的整数）。

### 样例 #1

#### 样例输入 #1

```
3 2
2 1 2 4
2 3 5 3
```

#### 样例输出 #1

```
428571
```

### 提示

在这个例子中，仅由一条路径从 $1$ 到 $N$。 它的流量为 $\min(3,4)=3$，花费为 $2+5=7$。

### 数据范围

测试点 $2\sim 5$ 满足 $N,M\le 100$。

对于 $100\%$ 的数据，$2 \leq N \leq 1000$，$1 \leq M \leq 1000$。

供题：Brian Dean

## 题解

### 分析

第一眼看到这个题目，以为是最短路板子，心想这题也能评绿。再一看发现这个最短路有两个评价指标，花费和流量。

设 $M$ 条管道需要花费 $C = \sum c_i$ ，流量 $F = \min(f_i)$ 。那么题目所求也就是 $\frac{C}{F}$ 的最大值，即 $\frac{\sum c_i}{\min(f_i)}$ ，且至少有一条由 $1$ 通往 $n$ 的路径。

不难发现若直接使用最短路枚举两个条件的最优解极其复杂，固考虑枚举流量 $1 \leq f_i \leq 1000$ ，再用 $c_i$ 为边权跑最短路模板，最后取最大值即可。如果当前边所对应的流量 $< f_i$ ，则跳过当前边。因为答案需要保证连通性，所以最后还需要判断能否到达 $n$ 点。

考虑使用 Dijkstra 堆优化为最短路算法，则时间复杂度为 $\Theta(n^2 \times \log n)$ ，极限情况约为 $10^7$ ，可以接受。

其实这道题也可以不用枚举 $1 \leq f_i \leq 100$ ，直接枚举 $M$ 条管道的流量即可，但对最终复杂度的变化不大，~~加上本人鸽子~~ ，就不优化了。

总的来说这道题没啥坑点，只要能想到枚举 $f_i$ 就不难通过，细节地方在代码里注释了。

## 代码

```cpp
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <memory.h>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6;
const int INF = 0x3f3f3f3f;

int n, m, ans;
int h[N], idx = 0;
int dis[N], vis[N];

struct Edge {
    int nxt, v, w, f;

    Edge()
    {
        this->nxt = -1, this->v = -1, this->w = INF, this->f = INF;
    }

    Edge(int _nxt, int _v, int _w, int _f)
    {
        this->nxt = _nxt, this->v = _v, this->w = _w, this->f = _f;
    }
} edges[N];

struct Node {
    int dis, vtx;

    Node(int _dis, int _vtx)
    {
        this->dis = _dis, this->vtx = _vtx;
    }

    friend bool operator<(Node x, Node y)
    {
        // 注意这个符号方向，我因为这个卡了好久
        return x.dis > y.dis;
    }
};

priority_queue<Node> q;

// 邻接表存图
void addEdge(int a, int b, int c, int f)
{
    idx++;
    edges[idx].v = b, edges[idx].nxt = h[a], edges[idx].w = c, edges[idx].f = f, h[a] = idx;
}

// Dijkstra 板子
void dijkstra(int u, int lim)
{
    dis[u] = 0;
    q.push(Node(0, u));
    while (!q.empty()) {
        Node cur = q.top();
        q.pop();
        int tmp = cur.vtx;
        if (vis[tmp])
            continue;
        vis[tmp] = 1;
        int p = h[tmp];
        while (p != -1) {
            // 当前管道流量过小，忽略
            if (edges[p].f < lim) {
                // 下面这行也要注意，我一开始没加就死循环了
                p = edges[p].nxt;
                continue;
            }
            if (dis[tmp] + edges[p].w < dis[edges[p].v]) {
                dis[edges[p].v] = dis[tmp] + edges[p].w;
                if (!vis[edges[p].v])
                    q.push(Node(dis[edges[p].v], edges[p].v));
            }
            p = edges[p].nxt;
        }
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c, f;
        cin >> a >> b >> c >> f;
        addEdge(a, b, c, f);
        addEdge(b, a, c, f);
    }
    for (int i = 1; i <= 1000; i++) {
        // 别忘了初始化
        memset(dis, 0x3f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dijkstra(1, i);
        if (dis[n] != INF)  // 判断能否到达 n
            ans = max(ans, i * M / dis[n]);
    }
    cout << ans << endl;
    return 0;
}
```

AC++！

[最短路] P5837 Milk Pumping G 题解


## 题目

链接：<http://182.254.140.138:8888/p/621>

### 说明

有四个人，每人身上的衣服分别有s1,s2,s3和s4处破损,而且每处破损程度不同,破损程度用需修好它用的时间表示(A1...As1,B1...Bs2,C1...Cs3,D1...Ds4)。不过你可以同时修补2处破损。但是这2处破损，只能是同一件衣服上的。就是说你只能同时修补一件衣服，修好了，才能修补下一件。

### 输入格式

本题包含5行数据：第1行，为s1,s2,s3,s4(1≤s1,s2,s3,s4≤20) 第2行，为A1...As1 共s1个数，表示第一件衣服上每个破损修好它所需的时间 第3行，为B1...Bs2 共s2个数，表示第二件衣服上每个破损修好它所需的时间 第4行，为C1...Cs3 共s3个数，表示第三件衣服上每个破损修好它所需的时间 第5行，为D1...Ds4 共s4个数，表示第四件衣服上每个破损修好它所需的时间 (1≤A1...As1,B1...Bs2,C1...Cs3,D1...Ds4≤60)

### 输出格式

输出一行,为修好四件衣服所要的最短时间。

### 样例

#### 输入数据 1

```input1
1 2 1 3		
5
4 3
6
2 4 3
```

#### 输出数据 1

```output1
20
```

## 题解

### 分析

一道 DP 题。

> 就是说你只能同时修补一件衣服，修好了，才能修补下一件。

这段话相当于明示了这四件衣服互不相干，可以拆分成四个子问题分别求解。

注意到可以同时修补一件衣服上的两个破洞，所以枚举情况的时候只需要枚举 $\frac{sum}{2}$ 种时间情况即可。

在进行 DP 之前需要先将 $a$ 数组升序排序，这样后面枚举状况的时候就可以直接枚举一大一小两处破损了。

转移方程式：

$$
dp_{i,j} =
\begin{cases}
dp_{i - 1, j}\hspace{5mm}& j < a_i\\
\max(dp_{i - 1, j}, dp_{i - 1, j - a_i} + a_i) & \text{otherwise}
\end{cases}
$$

注意所有的取最值操作都是 $\max$ ，必须取修复两处破损的最大时间为同时修补这两处破损的总时间。

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 1010;

int a[N], dp[N][N], ans, s[5];

int main() {
    for (int i = 1; i <= 4; i++)
        cin >> s[i];

    for (int k = 1; k <= 4; k++) {
        int n = s[k], sum = 0, partialAns = 0;
        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }

        sort(a + 1, a + n + 1);

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= sum / 2; j++) {
                dp[i][j] = dp[i - 1][j];

                if (j >= a[i])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i]] + a[i]);

                partialAns = max(partialAns, dp[i][j]);
            }
        }

        ans += max(partialAns, sum - partialAns);
    }

    cout << ans << endl;
    return 0;
}
```

AC++！


[DP] 补圣衣 题解


## 题目

链接：http://182.254.140.138:8888/p/617

### 说明

你现在拿到了许多的礼物，你要把这些礼物放进袋子里。你只有一个最多装下V 体积物品的袋子，你不能全部放进去。你也拿不动那么重的东西。你估计你能拿的最大重量为 G。现在你了解了每一个物品的完美值、重量和体积，你当然想让袋子中装的物品的完美值总和最大，你又得计划一下了。

### 输入格式

第一行：G 和 V 表示最大重量和体积。 第二行：N 表示拿到 N 件礼物。 第三到N+2行：每行3个数 Ti Gi Vi 表示各礼物的完美值、重量和体积

### 输出格式

输出共一个数，表示可能获得的最大完美值。

### 样例

#### 输入数据 1

```input1
6 5		
4		
10 2 2		
20 3 2
40 4 3
30 3 3
```

#### 输出数据 1

```output1
50
```

### 提示

对于20%的数据 N，V，G，Ti，Vi，Gi≤10
对于50%的数据 N，V，G，Ti，Vi，Gi≤100
对于80%的数据 N，V，G，Ti，Vi，Gi≤300
80%到100%的数据是N，V，G，Ti，Vi，Gi≤380 的离散随机数据。

## 题解

### 分析

第一眼看上去像 01 背包问题，但是仔细一看发现有两个条件（ 01 背包只有一个重量限制，这个有重量和体积）。01 背包的基础上多加一维体积就可以了。

$dp_{i,j}$  表示当前装的重量为 $i$ ，体积为 $j$ 。转移方程式如下：


$$
current_G = gifts_k.g, \ current_V = gifts_k.v
$$

$$
dp_{i,j} = \max(dp_{i,j}, dp_{i - current_G,j - current_V} + gifts_k.t)
$$

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 400;

int g, v, n, ans;
int dp[N][N];

struct Gift {
    int t, g, v;
} gifts[N];

int main() {
    cin >> g >> v >> n;

    for (int i = 1; i <= n; i++) {
        cin >> gifts[i].t >> gifts[i].g >> gifts[i].v;
    }

    for (int k = 1; k <= n; k++) {  // 当前礼物
        for (int i = g; i >= gifts[k].g; i--) {  // 当前重量
            for (int j = v; j >= gifts[k].v; j--) {  // 当前体积
                dp[i][j] = max(dp[i][j], dp[i - gifts[k].g][j - gifts[k].v] + gifts[k].t);
            }
        }
    }

    cout << dp[g][v] << endl;
    return 0;
}
```

AC++, rp++!


[DP] 打包 题解




## 题目

链接：<http://182.254.140.138:8888/p/216>

### 题目说明

很多人都曾经听说过数独，但你是否听说过数谜（Karuro）呢？实际上，数谜是数独的更大（且更难）的兄弟问题，而且在日本也是非常受欢迎的。

数谜问题和填字游戏类似，不过它要填的不是文字而是数字。数谜游戏的目标是用 $1 ～\ 9$ 填满所有空格，且这些数字相加的和满足相应的要求（或者称为“提示”），且在同一栏（“栏”是指一些水平或者竖直的连续的空格，用于提示的格子不算空格）不能填重复的数字。当所有格子按要求被填满后，这个数谜就看作被解决了。图 1 和图 2 是一个可能的数谜游戏示例。

![img](https://www.freesion.com/images/558/786845b3b03367143ec7327c0c169bde.JPEG)

当然，直接求解数谜问题的话会比较困难。所以现在我们需要解决的是一个更简单的数谜问题。简单数谜的形状是一个 $(n+1)$ 行乘 $(m+1)$ 列的矩形。而简单数谜也只有两种要求，就是行要求和列要求，且分别处于第一行和第一列，其他格子则是空格，而左上角是忽略不计的。coolzzz 同学爱好简单数谜，他已经给一些简单数谜填好了其中的一些空格。现在，他想寻求你的帮助，来帮他完成这些简单数谜。如图 3 所示，2 和 9 是 coolzzz 同学已经填好的空格，图 4 则是一个基于图 3 的一个可能的解答。

### 输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$ ，表示测试数据数目。每组数据第一行是 $n\ (n< 10)$ 和 $m\ (m< 10)$，表示数谜的形状的大小。接下来一行有 $n$ 个整数，是相应的行要求；然后一行是 $m$ 个整数，是相应的列要求。接下来的 $n$ 行每行有 $m$ 个小于 $10$ 的非负整数，0 表示该空格还没有被填数字，其他表示 coolzzz 同学已经填好的数字。输入数据保证未填数字的空格不会超过 $16$ 个。

### 输出格式

对于每组测试数据，输出若干行。如果基于 coolzzz 已填的结果，该数谜只有一个解，则输出该解；如果不止一个解，则输出一行 `Not unique.`；如果没有解，则输出一行 `No answer.`。

### 样例

#### 输入样例 1

```
3
3 3
6 6 6
6 6 6
0 0 0
0 3 0
0 0 0
2 3
10 17
5 16 6
2 0 0
0 9 0
2 2
3 5
4 4
0 0
0 0
```

#### 输出样例 1

```
Not unique.
2 7 1
3 9 5
No answer.
```

## 题解

### 分析

空着的格子数量 $\leq 16$ ，果断考虑爆搜。基本上就是八皇后的进阶版，注意每个测试样例的初始化和 DFS 的回溯就行。

### 代码

```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <map>
#include <set>
using namespace std;
const int N = 15;

// ans 答案数目，solved 当前解
int n, m, mp[N][N], T, ans, solved[N][N];
// column_sum[i] 第i行的和，row_sum[i] 第i列第和，exists_on_column[i][j] 在第i行是否存在j这个数字，exists_on_row[i][j] 在第i列是否存在j这个数字
int column_sum[N], row_sum[N], exists_on_column[N][N], exists_on_row[N][N];
// column_req 存储行要求，row_req 存储列要求（分别是输入第1、2行）
int column_req[N], row_req[N];

struct Point {
    int x, y;

    Point(int _x, int _y) {
        this -> x = _x, this -> y = _y;
    }
};

void init() {
    ans = n = m = 0;
    memset(mp, 0, sizeof(mp));
    memset(column_req, 0, sizeof(column_req));
    memset(row_req, 0, sizeof(row_req));
    memset(column_sum, 0, sizeof(column_sum));
    memset(row_sum, 0, sizeof(row_sum));
    memset(solved, 0, sizeof(solved));
    memset(exists_on_column, 0, sizeof(exists_on_column));
    memset(exists_on_row, 0, sizeof(exists_on_row));
}

void dfs(Point cur) {
    // 已经有多个解了就没必要继续搜了
    if (ans >= 2)
        return;

    // 搜到头了
    if (cur.x > n) {
        bool is_valid = 1;

        // 检查当前解是否合规 
        for (int i = 1; i <= n; i++) {
            if (column_sum[i] != column_req[i]) {
                is_valid = 0;
                break;
            }
        }

        if (!is_valid)
            return;

        for (int i = 1; i <= m; i++) {
            if (row_sum[i] != row_req[i]) {
                is_valid = 0;
                break;
            }
        }

        if (!is_valid)
            return;

        // 合规
        ans++;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                solved[i][j] = mp[i][j];
        }

        return;
    }

    // 一行一行地搜
    if (cur.y > m) {
        dfs(Point(cur.x + 1, 1));
        return;
    }

    // 当前数字填过了
    if (mp[cur.x][cur.y] != 0) {
        dfs(Point(cur.x, cur.y + 1));
        return;
    }

    // 没填过，现在填
    for (int i = 1; i <= 9; i++) {
        if (!exists_on_column[cur.x][i] && !exists_on_row[cur.y][i] && column_sum[cur.x] + i <= column_req[cur.x] &&
                row_sum[cur.y] + i <= row_req[cur.y]) {  // 当前值是否合法
            exists_on_column[cur.x][i] = 1;
            exists_on_row[cur.y][i] = 1;
            column_sum[cur.x] += i;
            row_sum[cur.y] += i;
            mp[cur.x][cur.y] = i;
            dfs(Point(cur.x, cur.y + 1));
            // 注意回溯
            exists_on_column[cur.x][i] = 0;
            exists_on_row[cur.y][i] = 0;
            column_sum[cur.x] -= i;
            row_sum[cur.y] -= i;
            mp[cur.x][cur.y] = 0;
        }
    }
}

int main() {
    cin >> T;

    while (T--) {
        init();  // 初始化
        cin >> n >> m;

        for (int i = 1; i <= n; i++)
            cin >> column_req[i];

        for (int i = 1; i <= m; i++)
            cin >> row_req[i];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> mp[i][j];
                column_sum[i] += mp[i][j];
                row_sum[j] += mp[i][j];
                exists_on_column[i][mp[i][j]] = 1;
                exists_on_row[j][mp[i][j]] = 1;
            }
        }

        dfs(Point(1, 1));  // 左上角开始搜

        if (ans == 0) {
            cout << "No answer." << endl;
            continue;
        }

        if (ans > 1) {
            cout << "Not unique." << endl;
            continue;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cout << solved[i][j] << " ";
            }

            cout << endl;
        }
    }

    return 0;
}
```

AC++！

标签 OI

标签为 OI 的文章

浅谈并查集

浅谈差分约束

浅谈乘法逆元

浅谈概率

浅谈分层图最短路

浅谈 Tarjan

ICPC 2023 西安站游记

CSP-J 2022 题解

wjr的有根树题解

浅谈树状数组

浅谈堆

[图论] UVA10000 Longest Paths 题解

浅谈 ST 表

[DP] P1077 [NOIP2012 普及组] 摆花题解

[图论] P1522 [USACO2.4] 牛的旅行 Cow Tours 题解

[最短路] P5837 Milk Pumping G 题解

[DP] 补圣衣题解

[DP] 打包题解

简单数迷题解

Sam Zhang.

标签 OI

标签为 OI 的文章

浅谈并查集

浅谈差分约束

浅谈乘法逆元

浅谈概率

浅谈分层图最短路

浅谈 Tarjan

ICPC 2023 西安站游记

CSP-J 2022 题解

wjr的有根树 题解

浅谈树状数组

浅谈堆

[图论] UVA10000 Longest Paths 题解

浅谈 ST 表

[DP] P1077 [NOIP2012 普及组] 摆花 题解

[图论] P1522 [USACO2.4] 牛的旅行 Cow Tours 题解

[最短路] P5837 Milk Pumping G 题解

[DP] 补圣衣 题解

[DP] 打包 题解

简单数迷 题解

Sam Zhang.

wjr的有根树题解

[DP] P1077 [NOIP2012 普及组] 摆花题解

[DP] 补圣衣题解

[DP] 打包题解

简单数迷题解