题解：AT_agc032_b [AGC032B] Balanced Neighbors

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

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

不连通

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

节点编号加上节点邻接的编号为定值

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

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

代码放一下。

CPP

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

题解：AT_agc032_b [AGC032B] Balanced Neighbors

文章操作

相关推荐

评论

题解：AT_agc032_b [AGC032B] Balanced Neighbors