自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:27:09，当前版本为作者最后更新于2020-11-08 18:19:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$$\color{Red}\sf dWoi\ Round\ 1\ A\ Physics\ Problem $$

Description

给定一个 $n$ 点 $k$ 边的连通无向图，求有多少组满足要求的点对使得这两个点之间的最短路长度大于 $1$。
$1 \le n,k \le 10^7$，$1 \le u_i,v_i \le n$，保证无重边无自环

Subtask 1

约束条件：$n \le 2$。

当 $n \le 2$ 时，不存在满足要求的点对使得最短路长度大于 $1$，因此输出 $0$。

Subtask 2

约束条件：该图是一条链。

每一个点 $p$ 都可以往他的右边找到 $n-p-1$ 个点，因此答案为：

$$\sum\limits_{i=1}^{n-2}n-i-1$$

Subtask 3

约束条件：该图是一个菊花图。

和链差不多，就不说了，其实是书虫太懒没写

Subtask 4

约束条件：$n,k \le 1000$。

有一个奇怪的 $\mathcal O(n^2)$ 做法，也就是枚举所有点对然后判断他们在不在同一条边（

应该能过，放的很水。

Subtask 5

这题把连通，无重边，无自环都限制了，题目就简单 1w 倍了。

首先我们先任意选择两个点形成的点对，应该有 $\textsf C_n^2$ 种选择方法，然后我们要把 $k$ 条边直接相连的点对个数减掉，也就是减掉 $k$，所以最终答案为：

$$\textsf C_n^2-k=\dfrac{n \times (n-1)}{2}-k$$

直接 $\mathcal O(1)$。

Code

#include <bits/stdc++.h>

using namespace std;

int main () {
	long long n, k;
	scanf("%lld%lld", &n, &k);
	printf("%lld", n *(n - 1) / 2 - k);
	return 0;
}