首页 > 代码库 > zoj1967 poj2570 Fiber Network (floyd算法)
zoj1967 poj2570 Fiber Network (floyd算法)
虽然不是最短路，但是询问时任意两点之间的信息都要知道才能回答，由此联想到floyd算法，只要都floyd算法的原理理解清楚了就会发现：这道题的思想和求任意两点之间的最短路的一样的，只不过是更新的信息不同而已。
这道题还有一个难点在于状态压缩：如果直接用字符串来表示maps[i][j],那么在floyd中还需要再加一层循环来找maps[i][k]和maps[k][j]有哪些一样的字母，这样时间复杂度太高，实际测试表明会TLE。那么可以用状态压缩的技巧，用二进制表示集合，最多就26位（代表26个字母），那么在floyd算法实现过程中只需要一些位运算就解决问题了。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=200+10;int n,a,b;int maps[maxn][maxn];void floyd();int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d",&n)==1&&n) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { maps[i][j]=0; } } while(scanf("%d%d",&a,&b)==2) { if(a==0&&b==0) break; char str[205]="0"; scanf("%s",str); int len=strlen(str); for(int i=0;i<len;i++) { int t=str[i]-‘a‘; maps[a][b]|=(1<<t); } } floyd(); while(scanf("%d%d",&a,&b)==2) { if(a==0&&b==0) { printf("\n");break; } if(maps[a][b]==0) { printf("-\n"); } else { for(int i=0;i<26;i++) { if(maps[a][b]&(1<<i)) { printf("%c",‘a‘+i); } } printf("\n"); } } } //fclose(stdin); //fclose(stdout); return 0;}void floyd(){ for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if((maps[i][k]!=0)&&(maps[k][j]!=0)) { maps[i][j]|=maps[i][k]&maps[k][j]; } } } }}
zoj1967 poj2570 Fiber Network (floyd算法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。