题目大意
构造一张无向图，使得从 \(1\) 到 \(2\) 的最短路数量为 \(k\)。
思路分析
我们首先可以发现当 \(k = 2^t\) 时的构造方式：
其中只有 \(O(\log k)\) 个点。
当 \(k\not = 2^t\) 时，我们可以将 \(k\) 二进制拆分，对于每一个二进制位重复上述操作，就可以得到：
当然，为了保证最短路长度相同，少的部分需要用一条链补齐。
算一下发现点数为 \(O(\log^2k)\)，当 \(k\) 达到极限数据 \(2^{29}-1\) 时点数会超过 \(1000\)，无法通过。
我们发现，那些用链补齐的部分是相当浪费的，也就是说，我们可以将所有用于补齐的链合并成一条：
这样我们的点数虽然依然是 \(O(\log^2 k)\) 的，但减少了一部分点，在极限数据时只需要 \(900\) 个点，可以通过。
代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 2010, M = 50;
#define inf 0x3f3f3f3f
int n, k, len, tot = 3;
int G[N][N], a[M], need[M];
void add(int u, int v){
G[u][v] = G[v][u] = 1;
}
void solve(int x){
int num = tot;
if (x == 0) {
add(num, num + 1);
add(num + 1, num + 2);
add(num + 2, num + 3);
tot += 3;
if (x == len - 1) add(num + 3, 2);
else add(num + 3, need[len - 3]);
return ;
}
if (x == 1) {
add(num, num + 1);
add(num, num + 2);
add(num + 1, num + 3);
add(num + 2, num + 4);
add(num + 3, num + 5);
add(num + 4, num + 5);
tot += 5;
if (x == len - 1) add(num + 5, 2);
else add(num + 5, need[len - 3]);
return ;
}
add(num, num + 1);
add(num, num + 2);
tot += 2;
for (int i = 1; i < x; i ++) {
add(tot - 1, tot + 1);
add(tot - 1, tot + 2);
add(tot, tot + 1);
add(tot, tot + 2);
tot += 2;
}
add(tot - 1, tot + 1);
add(tot, tot + 1);
tot ++;
add(tot, need[len - x - 1]);
}
int main(){
cin >> k;
while (k) {
a[++ len] = (k & 1);
k >>= 1;
}
for (int i = 1; i <= len; i ++) add(tot, tot + 1), tot ++;
add(tot, 2);
need[0] = 2;
for (int i = 1; i <= len; i ++) need[len - i + 1] = i + 3;
for (int i = 1; i <= len; i ++)
if (a[i]) {
add(1, ++ tot);
solve(i - 1);
}
printf("%d\n", tot);
for (int i = 1; i <= tot; i ++) {
for (int j = 1; j <= tot; j ++)
printf("%c", G[i][j] ? 'Y' : 'N');
printf("\n");
}
return 0;
}