算法实战：模幂、构造、背包、贪心及堆维护六题精析

2. System Administrator（系统管理员）

题目： CF22C System Administrator

解法：构造

要满足题目要求：去掉一个点后，图不连通，那么就构造一个点 v 左边连一个点，右边连 n - 2 个点。因为这道题目的边有限，且要用完，这种方式连的边最多，且满足题目要求。

重要的性质：

n 个点如果至少要连 n - 1 条边，所以 m < n - 1 时，连通图就不存在。所以 m > n - 1；

当有一个顶点与 v 相连，并且与其他顶点都不相连时，最大的边数可由以下方法来求：对于一个无向图，n 个顶点，最多有 n(n - 1) / 2 条边。（结论），因为每一个点可以和剩下的 n-1 个点连一条边，那么就是 n(n - 1)，且因为两个点只有一条无向边，会多算一次就/2。综上，可以算满足题目要求的情况：一个点连左边一个点，边数 1，这个点加上右边一共 n - 1 个点边数 (n - 1) * (n - 2) / 2 + 1。所以 m < (n - 1) * (n - 2) / 2 + 1。

综上所述，n - 1 < m < (n - 1) * (n - 2) / 2 + 1，可以用于判断 m 是否合法。

如果 m 在范围内，那么图存在，一定能构造出来，可以先在 v 的左边放置一个顶点 w，在另一边放剩余的 n-2 个点，将所有的点 (除了 v 本身)，连在 v 上，然后将它们（除了 w）相互连接起来。

代码：

#include <iostream>
using namespace std;
typedef long long LL;

LL n, m, v;

int main() {
    cin >> n >> m >> v;
    if (m < n - 1 || m > (n - 1) * (n - 2) / 2 + 1) {
        cout << -1 << endl;
    } else {
        // 此处省略具体建图逻辑，核心在于判断范围
        // 若需输出方案，按上述构造思路输出即可
    }
    return 0;
}