POJ2570 二进制，位运算，Floyd

题意：

给你一个有向图，两点之间有多种连接方式，然后每次询问都问你点A,B之间有哪些方式可以到达，每个小字母是一个方式.

思路：

很巧妙的位运算和Floyd应用，借助Floyd的更新过程，去更新任意两组边组合起来的长边，如 map[i][j] 是由 map[i][k] 和 map[k]][j]接起来的，更新方式很容易理解，是map[i][j] = map[i][j] | (map[i][k] & map[k][j]),每条边的状态都转化成2进制就行了。

#include<stdio.h>

#include<string.h>

int map[205][205];

int Pow(int n)

{

   int p = 1;

   for(int i = 1 ;i <= n ;i ++)

   p *= 2;

   return p;

}

int main ()

{

   int n;

   int a ,b ,l ,i ,j ,k;

   char str[100];

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

   {

      memset(map ,0 ,sizeof(map));

      while(scanf("%d %d" ,&a ,&b) && a + b)

      {

         scanf("%s" ,str);

         l = strlen(str);

         for(i = 0 ;i < l ;i ++)

         map[a][b] += Pow(str[i] - 'a');

      }

      for(k = 1 ;k <= n ;k ++)

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= n ;j ++)

      map[i][j] = map[i][j] | (map[i][k] & map[k][j]);

      while(scanf("%d %d" ,&a ,&b) && a + b)

      {

         int mk = 0;

         for(i = 0 ;i < 26 ;i ++)

         {

            if(map[a][b] & Pow(i))

            {

               printf("%c" ,'a' + i);

               mk = 1;

            }

         }

         if(!mk) printf("-");

         printf("\n");

      }

      printf("\n");

   }

   return 0;

}

巴特西

POJ2570 二进制，位运算，Floyd

最新文章

热门文章