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