Codeforces Round #228 (Div. 1) 388B Fox and Minimal path

链接：http://codeforces.com/problemset/problem/388/B

【题意】

给出一个整数K，构造出刚好含有K条从1到2的最短路的图。

【分析】

由于是要自己构造图，当然构造的方法很多了，需要考虑简单性和可行性。出于简单考虑，图中从1到2的所有路径都是最短路，为了保证路径长度一样，在构图时就需要分层次，使得每一层的点距离上一层的点的距离都是一个单位。

那么如何使得路径条数刚好为K呢，这里涉及到相邻层次的点的链接方式。比如说每个点和上一层的所有点都有链接，那么这样总的路径数就是每层点的个数乘起来，但是这很难保证乘起来的值刚好是K，于是想到进制数的方法，可以构造出不同底数的链接模型，最后串联起来，起到相加作用，最后一定能凑成K。好需要注意的是点的个数，如果层次分的少了点的个数就多了，超过限制就错了。

不过我在这里不用上面那种拼接方式，而是使用种更巧妙地构图，这种图有许多很好的性质，说不定有其它的用途，我就不用文字说明了，看图：

【代码】

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <cmath>

 #include <vector>

 using namespace std;

 int cnt[];

 long long dp[];

 bool g[][];

 int k;

 int top;

 void addedge(int a,int b)

 {

     g[a][b]=g[b][a]=true;

 }

 void work(int c)

 {

     vector<int> fin;

     int p=,offset;

     while (p<=c)

     {

         int t=top;

        for (;top<t+p;++top)

          addedge(top,top-p);

        for (offset=top-*p;offset<top-p;++offset)

           addedge(offset,top);

        ++top;

        ++p;

     }

     for (offset=top-p;offset<top;++offset)

       fin.push_back(offset);

     for (int i=fin.size()-;i>=;--i)

     {

         int t=i-;

         if (t<) t=;

         if ((<<t)<=k)

         {

             k-=(<<t);

             addedge(,fin[i]);

         }

     }

     --top;

     printf("%d\n",top);

     for (int i=;i<=top;++i)

     {

        for (int j=;j<=top;++j)

        if (g[i][j]) printf("Y"); else printf("N");

        printf("\n");

     }

 }

 int main()

 {

     while (~scanf("%d",&k))

     {

         memset(g,,sizeof g);

         addedge(,);

         addedge(,);

         top=;

         int c=,tem=k;

         while (tem){++c;tem>>=;}

         work(c);

     }

 }

巴特西

Codeforces Round #228 (Div. 1) 388B Fox and Minimal path

最新文章

热门文章