題目鏈接

題意

判斷$N$個點能否構建一個自補圖。
補圖：將圖$G$添加一些邊使$G$變成完全圖，這些邊構成的就是$G$的補圖
同構圖：圖$G$和$H$的同構是$G$和$H$的頂點集之間的雙射，同構圖的結點數必須相同，結構必須相同。
自補圖： 圖$G$若和它的補圖$G^{\prime }$，則$G$為自補圖

思路

• 圖同構首先邊要一樣多，又要滿足補圖同構，所以完全圖的邊數要是4的倍數
• 四個點的自補圖
  
• 對于一個自補圖G我們每次可以加4個點進行擴充
  

#include <bits/stdc++.h> const int maxn = 2e3 + 2; using namespace std; int f[maxn], g[maxn][maxn]; int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T, Case = 1;cin >> T;while (T--) {cout << "Case #" << Case++ << ": "; int n;cin >> n;if (n % 4 > 1) {cout << "No\n";continue;}cout << "Yes\n";for (int i = 1; i <= n; ++i) {f[i] = i;for (int j = 1; j <= n; ++j) {g[i][j] = 0;}}for (int i = 1; i <= n/4; ++i) {g[i*4-3][i*4-2] = g[i*4-2][i*4-3] = 1;g[i*4-2][i*4-1] = g[i*4-1][i*4-2] = 1;g[i*4-1][i*4] = g[i*4][i*4-1] = 1;for (int j = 1; j <= i*4-4; ++j) {g[j][i*4-2] = g[i*4-2][j] = 1;g[j][i*4-1] = g[i*4-1][j] = 1;}}for (int i = 1; i <= n/4; ++i) {int j = i*4 - 3;swap(f[j], f[j+1]);swap(f[j+1], f[j+3]);swap(f[j+2], f[j+3]);}if (n & 1) {for (int i = 1; i <= n/4; ++i) {g[n][i*4-2] = g[i*4-2][n] = 1;g[n][i*4-1] = g[i*4-1][n] = 1;}}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cout << g[i][j];}cout << endl;}for (int i = 1; i <= n; ++i) {if (i > 1) cout << " ";cout << f[i];}cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第六场）E - Androgynos (构建自补图)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。