题解：AT_agc032_b [AGC032B] Balanced Neighbors

· · 题解

这是一篇作为补充的题解。

首先，做法是正难则反的构造补图，详细可以看第一篇题解。那么我解释一下我们构造正的图的两个条件是如何产生的。

这个简单，题目要求连通，那么我们构造的图就要不连通，这样补图才能连通。

可以发现，做到了这一点之后生成补图，对于每个节点它的邻接总值就是所有节点编号和减去这个定值。定值减定值仍然是定值。

至于为什么要加上节点编号本身，是因为你压根就构造不出来一个不连通的，而且邻接节点编号和一定的图。不信你可以自己试试。

代码放一下。

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 105;
int n, dir[N][N];
int main() {
    cin >> n;
    cout << (n * (n - 1) >> 1) - (n >> 1) << '\n';
    if(n & 1) {
        rep(i, 1, n >> 1) {
            dir[i][n - i] = dir[n - i][i] = 1;
        }
        rep(i, 1, n) {
            rep(j, i + 1, n) {
                if(!dir[i][j]) {
                    cout << i << ' ' << j << '\n';
                }
            }
        }
    }
    else {
        rep(i, 1, n >> 1) {
            dir[i][n - i + 1] = dir[n - i][i] = 1;
        }   
        rep(i, 1, n) {
            rep(j, i + 1, n) {
                if(!dir[i][j]) {
                    cout << i << ' ' << j << '\n';
                }
            }
        }
    }   
    return 0;
}