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++！

标签算法

标签为算法的文章

CSP-J 2022 题解

wjr的有根树题解

浅谈树状数组

浅谈堆

[图论] UVA10000 Longest Paths 题解

浅谈 ST 表

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

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

[最短路] P5837 Milk Pumping G 题解

[DP] 补圣衣题解

[DP] 打包题解

简单数迷题解

Sam Zhang.

标签 算法

标签为 算法 的文章

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] 打包题解

简单数迷题解