难得写的构造题,比赛的时候没写出来,听薛昊说的时候就理解了。
这种构图方法还是欠缺……
题意:
起点 1,终点 2,构造一个图,使得最短路数量为 k 。
思路:
这种题一般都是二进制分解做,关键就是构造出二进制的图,然后控制路径长度相同即可。这里提供一种构造方法。
点数最多 1e9 每行30个节点足够
AC Code
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
//#define DEBUG
using namespace std;
const int maxn = 110;
const int inf = 0x3f3f3f3f;
int k;
char mat[maxn][maxn];
int main()
{
for (int i = 1; i <= 100; i++)
for (int j = 1; j <= 100; j++)
mat[i][j] = 'N';
mat[2][11] = mat[11][2] = mat[1][41] = mat[41][1] = mat[1][71] = mat[71][1] = 'Y';
for (int i = 11; i < 40; i++)
mat[i][i + 1] = mat[i + 1][i] = 'Y';
for (int i = 41; i < 70; i++) {
mat[i][i + 1] = mat[i + 1][i] = 'Y';
mat[i][i + 30 + 1] = mat[i + 30 + 1][i] = 'Y';
}
for (int i = 71; i < 100; i++) {
mat[i][i + 1] = mat[i + 1][i] = 'Y';
mat[i][i - 30 + 1] = mat[i - 30 + 1][i] = 'Y';
}
scanf("%d", &k);
int len = log2(k) + 1;
for (int i = 1; i <= len; i++) {
if (k % 2)
mat[40 + i][11 + len - i] = mat[11 + len - i][40 + i] = 'Y';
k /= 2;
}
#ifndef DEBUG
puts("100");
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++)
putchar(mat[i][j]);
puts("");
}
#else
int dis[maxn][maxn], ans = 0;
for (int i = 1; i <= 100; i++)
for (int j = 1; j <= 100; j++)
dis[i][j] = mat[i][j] == 'Y' ? 1 : inf;
for (int k = 1; k <= 100; k++) {
for (int i = 1; i <= 100; i++)
for (int j = 1; j <= 100; j++) {
dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
}
}
for (int k = 3; k <= 100; k++) {
if (dis[1][k] + dis[k][2] == len + 2) {
ans++;
printf("k--> %d dis[1][k] --> %d dis[k][2] --> %d\n", k, dis[1][k], dis[k][2]);
}
}
//printf("min ----> %d ans ---> %d\n", p, ans);
printf("min --> %d ans ----> %d \n", dis[1][2], ans);
#endif
return 0;
}