POJ--2570--Fiber Network【floyd+位运算】

题意:一些公司决定搭建一些光纤网络,单向的,如果从第一点到第二点,有ab两个公司可以搭建,第二点到第三点有ac两个公司可以搭建,第一点到第三点有d公司可以搭建,则第一点到第三点有a、d两个公司可以搭建,a是通过第二点,d是直接连接两点。现在给你这么一个光纤网络,问某两点之间有哪些公司可以搭建起网络。


首先这题是个多源点的,有点像最短路的思想,如果让我做我肯定硬着头皮找相同的字母,不过我看到图论书里的想法很好,就写上来了。

因为公司是用一个小写字母来标识的,且每个公司的标识互不相同,也就是说最多只有26个公司,因此,可以用整数中的二进制位来表示每个公司,通过二进制位运算来实现集合的“或”运算和“与”运算。

如果第一点到第二点有a、b、c三个公司,则可用“00000000000000000000000000000111”来表示,第二点到第三点有a、d两个公司,则可用“00000000000000000000000000001001“来表示。所以如果用edge数组表示某两点之间的公司,就可以这么更新:

edge[i][j] |= edge[i][k] & edge[k][j]。

然后是输入输出的处理,在读入字符串后,要用逻辑左移存入到edge数组中:edge[a][b] = 1 << (s[i]-‘a‘)

输出的处理,枚举字符ch从‘a’到‘z’,如果edge[a][b]&(1<<ch-‘a‘)为1,则表示edge[a][b]所代表的集合中包含ch公司,则输出

如果edge[a][b]==0,说明a、b之间没有公司了


二进制和位运算真是好东西


#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 510
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson r,m+1,rt<<1|1

int n;
int edge[MAXN][MAXN];
char s[30];
void floyd(){
    int i,j,k;
    for(k=1;k<=n;k++){
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                edge[i][j] |= edge[i][k] & edge[k][j];
            }
        }
    }
}
int main(){
    int i,j;
    int a,b;
    while(scanf("%d",&n),n){
        memset(edge,0,sizeof(edge));
        while(scanf("%d%d",&a,&b),a||b){
            scanf("%s",s);
            int l = strlen(s);
            for(i=0;i<l;i++){
                edge[a][b] |= 1 << (s[i]-'a');
            }
        }
        floyd();
        while(scanf("%d%d",&a,&b),a||b){
            for(i=0;i<=26;i++){
                if(edge[a][b]&(1<<i))     printf("%c",'a'+i);
            }
            if(!edge[a][b]) printf("-");
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}


POJ--2570--Fiber Network【floyd+位运算】,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。