題意：
? ? ? 給你一個(gè)有向圖，兩點(diǎn)之間有多種連接方式，然后每次詢問(wèn)都問(wèn)你點(diǎn)A,B之間有哪些方式可以到達(dá)，每個(gè)小字母是一個(gè)方式.


思路：

? ? ? 很巧妙的位運(yùn)算和Floyd應(yīng)用，借助Floyd的更新過(guò)程，去更新任意兩組邊組合起來(lái)的長(zhǎng)邊，如 map[i][j] 是由 map[i][k] 和 map[k]][j]接起來(lái)的，更新方式很容易理解，是map[i][j] = map[i][j] | (map[i][k] & map[k][j]),每條邊的狀態(tài)都轉(zhuǎn)化成2進(jìn)制就行了。

#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; }

總結(jié)

以上是生活随笔為你收集整理的POJ2570 二进制，位运算，Floyd的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。