Description

给定n个点，m条边，k个标记点，hack掉给出的程序。

Solution

先考虑不可能hack掉的情况。当所有点都是标记点的时候肯定不能hack掉，也就是\(n=k\)。还有就是\(m > n * (n - 1) / 2 - k + 1\)（也就是最多可构造的边）。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

能hack的情况下，我们先将标记点与非标记点连起来，然后将非标记点与未加入图的边连起来，这样保证了图的联通性，最后随便加边凑到\(m\)条边

#include<bits/stdc++.h>
using namespace std;
int n, m, k, x, y, a[1100], b[1100], f[1100][1100];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    if (n == k || m > n * (n - 1) / 2 - k + 1) //不能hack掉的情况
        return printf("-1\n"), 0;
    for (int i = 1; i <= k; i ++) {
        scanf("%d", &a[i]);
        b[a[i]] = 1;
    }
    x = a[1];
    if (a[1] == 1) y = 2; else  y = 1;
    for (int i = y + 1; i <= n; i ++)
        if (i != x) {
            if (x == y)
                y ++;
            printf("%d %d\n", y, i);
            f[y][i] = f[i][y] = 1, m --; y ++;
        }
    for (int i = 1; m && i <= n; i ++)
        if (!b[i])
            f[x][i] = f[i][x] = 1, m --, printf("%d %d\n", x, i);
    for (int i = 1; m && i <= n; i ++)
        if (i != x)
            for (int j = i + 1; m && j <= n; j ++)
                if (j != x && !f[i][j]) {
                    f[i][j] = f[j][i] = 1, m --;
                    printf("%d %d\n", i ,j);
                }
    return 0;
}

/*
43 76 6
24 11 30 21 35 1
*/
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄