题意:
给n个点,要求构造出一个图G,使图G与其补图G'同构。
题解:
显然,同构的两个图的边数需要相等,所有只有当n阶完全图的边数为偶数时有解。
然后,我们可以分情况讨论:
- n=4k
- n=4k+1
对于两种情况,我们都可以先把点分为四部分A,B,C,D。首先把A和B构造成完全图,然后C中每个点与A中每个点相连,D中每个点与B中每个点相连。当n=4k+1时,多余的那个点与两个团相连。
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e3 + 3;
const ll inf = 0x7f7f7f7f7f7f7f7f;
int T, n;
int mp[MAXN][MAXN];
int f[MAXN];
int main()
{
scanf("%d", &T);
int icase = 0;
while (T--)
{
scanf("%d", &n);
memset(f, 0, sizeof(f));
memset(mp, 0, sizeof(mp));
int tmp = n * (n - 1) / 2;
if (tmp % 2)
{
printf("Case #%d: No\n", ++icase);
continue;
}
printf("Case #%d: Yes\n", ++icase);
for (int i = 1; i <= n / 2; i++)
for (int j = i + 1; j <= n / 2; j++)
mp[i][j] = mp[j][i] = 1;
for (int i = 1; i <= n / 4; i++)
for (int j = n / 2 + 1; j <= n / 4 * 3; j++)
mp[i][j] = mp[j][i] = 1;
for (int i = n / 4 + 1; i <= n / 2; i++)
for (int j = n / 4 * 3 + 1; j <= n / 4 * 4; j++)
mp[i][j] = mp[j][i] = 1;
for (int i = 1; i <= n / 2; i++)
f[i] = i + n / 2;
int temp = n / 4 * 4;
for (int i = n / 2 + 1; i <= n; i++)
f[i] = temp - i + 1;
if (n % 4 == 1)
{
for (int i = 1; i <= n / 2; i++)
mp[i][n] = mp[n][i] = 1;
f[n] = n;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
printf("%d", mp[i][j]);
puts("");
}
for (int i = 1; i <= n; i++)
if (i != n)
printf("%d ", f[i]);
else
printf("%d\n", f[i]);
}
return 0;
}