链接：http://codeforces.com/problemset/problem/388/B
【题意】
给出一个整数K，构造出刚好含有K条从1到2的最短路的图。
【分析】
由于是要自己构造图，当然构造的方法很多了，需要考虑简单性和可行性。出于简单考虑，图中从1到2的所有路径都是最短路，为了保证路径长度一样，在构图时就需要分层次，使得每一层的点距离上一层的点的距离都是一个单位。
那么如何使得路径条数刚好为K呢，这里涉及到相邻层次的点的链接方式。比如说每个点和上一层的所有点都有链接，那么这样总的路径数就是每层点的个数乘起来，但是这很难保证乘起来的值刚好是K，于是想到进制数的方法，可以构造出不同底数的链接模型，最后串联起来，起到相加作用，最后一定能凑成K。好需要注意的是点的个数，如果层次分的少了点的个数就多了，超过限制就错了。
不过我在这里不用上面那种拼接方式，而是使用种更巧妙地构图，这种图有许多很好的性质，说不定有其它的用途，我就不用文字说明了，看图：
【代码】
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <cmath> 5 #include <vector> 6 using namespace std; 7 int cnt[100]; 8 long long dp[100]; 9 bool g[1001][1001]; 10 int k; 11 int top; 12 void addedge(int a,int b) 13 { 14 g[a][b]=g[b][a]=true; 15 } 16 void work(int c) 17 { 18 vector<int> fin; 19 int p=2,offset; 20 while (p<=c) 21 { 22 int t=top; 23 for (;top<t+p;++top) 24 addedge(top,top-p); 25 for (offset=top-2*p;offset<top-p;++offset) 26 addedge(offset,top); 27 ++top; 28 ++p; 29 } 30 for (offset=top-p;offset<top;++offset) 31 fin.push_back(offset); 32 for (int i=fin.size()-1;i>=0;--i) 33 { 34 int t=i-1; 35 if (t<0) t=0; 36 if ((1<<t)<=k) 37 { 38 k-=(1<<t); 39 addedge(2,fin[i]); 40 } 41 } 42 --top; 43 printf("%d\n",top); 44 for (int i=1;i<=top;++i) 45 { 46 for (int j=1;j<=top;++j) 47 if (g[i][j]) printf("Y"); else printf("N"); 48 printf("\n"); 49 } 50 } 51 int main() 52 { 53 while (~scanf("%d",&k)) 54 { 55 memset(g,0,sizeof g); 56 addedge(3,1); 57 addedge(4,1); 58 top=5; 59 int c=0,tem=k; 60 while (tem){++c;tem>>=1;} 61 work(c); 62 } 63 }