TOJ---1141---warShall传递闭包

好多事.....

特别是心事....

总是爱追忆自己亲手丢掉的东西.....

-------------------华丽丽的分界线---------------------

好现在来看这个题目吧：

　　　　touch me

当时题目是读懂了就是纠结在字符串的存储与读取上然后就这样被卡主了...

后来参考了下面2篇博客帮助很大写的很好

http://blog.csdn.net/classicbear/article/details/7608410

http://www.cnblogs.com/jackge/archive/2013/05/01/3053285.html

给我感觉就是位运算真的很有用有必要好好掌握一下 and 将字母进行移位运算这个hash 非常好

虽然这个下面代码很水但给出的注释i 可能有助于你的理解

 1 // warShall 传递闭包
 2 
 3 #include <iostream>
 4 #include <map>
 5 using namespace std;
 6 
 7 const int size = 220;
 8 char str[size];
 9 int mp[size][size];
10 
11 void warShall( int n )
12 {
13     for( int k = 1 ; k<=n ; k++ )
14     {
15         for( int i = 1 ; i<=n ; i++ )
16         {
17             for( int j = 1 ; j<=n ; j++ )
18             {
19                 if( mp[i][k]&mp[k][j] ) // 只有 2个二进制在某位上都是1 值在该位上才是1 可以判断段 i->k  与  k->j 是否有相同的顶点即 作为 i->j的桥梁
20                 {
21                     mp[i][j] = mp[i][j] | ( mp[i][k]&mp[k][j] ); // 存在一个k是i->j的桥梁 则将其加入 i->j的可以到达的方式中 以位运算结果存储
22                 }
23             }
24         }
25     }
26 }
27 
28 void slove( int value )
29 {
30     int cnt = 0;
31     if( value )
32     {
33         while( value )
34         {
35             if( value&1 ) // 从低至高 一位一位进行判断 即a~z的判断 &1就是判断最低位1 是否为1 即可以判断是否有字幕存在 即是否可以连接
36             {
37                 printf( "%c",'a'+cnt );
38             }
39             value>>=1; // &1 了 就右移一位 最低位的1被舍弃
40             cnt++;
41         }
42     }
43     else
44     {
45         printf( "-" );
46     }
47     printf( "
" );
48 }
49 
50 int main()
51 {
52     int n;
53     int st , end;
54     while( ~scanf("%d",&n) &&n )
55     {
56         memset( mp , 0 , sizeof(mp) );
57         while(1)
58         {
59             scanf( "%d %d",&st,&end );
60             if( !st && !end )
61                 break;
62             scanf( "%s",str );
63             for( int i = 0 ; str[i]!='' ; i++ )
64             {
65                 mp[st][end] = mp[st][end] | ( 1<<(str[i]-'a') ); // 或 运算 任何一个二进制中的某位上是1 则 值在该位上也是1
66             }
67         }
68         warShall( n );
69         while(1)
70         {
71             scanf( "%d %d",&st,&end );
72             if( !st && !end )
73                 break;
74             slove( mp[st][end] );
75         }
76         printf( "
" ); // 输出格式要求
77     }
78     return 0;
79 }

View Code

today:

　　世间每一次相逢都是久别重逢

just follow your heart