dWoi Round 1 A 题解

· · 题解

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

Description

给定一个 n 点 k 边的连通无向图，求有多少组满足要求的点对使得这两个点之间的最短路长度大于 1。

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;
}