本文主要是介绍zoj 1967 poj 2570 Fiber Network，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个站点，站点与站点之间有一些公司负责线路线路，查询所有可以提供从站点a到的站点b的线路连接的公司。
思路：用floyd的思想求解，将递推公式修改为 a[i][j] |= a[i][k] & a[k][j]。这题运用二进制表示集合可以方便的求解，因为公司只用小写字母表示，所以最多只有26个公司，用一个整数就可以表示这个集合。求解路径时，我们求得不是最短路径，而是求这条路径上集合的交集然后并上其他路径上的交集。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;const int maxn = 205;int n;
int a[maxn][maxn];bool input(){scanf("%d",&n);if(!n) return false;int u,v;char w[30];//清零 for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){a[i][j] = 0;}}while(1){scanf("%d%d",&u,&v);if(u + v == 0) break;scanf("%s",&w);for(int i = 0; i < strlen(w); i++)a[u][v] |= (1<<w[i]-'a');}return true;
}void solve(){for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){a[i][j] |= a[i][k] & a[k][j];}}}int u,v;while(1){scanf("%d%d",&u,&v);if(u + v == 0) break;if(a[u][v]){for(int i = 0; i < 26; i++){if(a[u][v] & (1<<i)) putchar('a'+i);}}else{putchar('-');}puts("");}puts("");
}int main(){while(input()){solve();}return 0;
}这篇关于zoj 1967 poj 2570 Fiber Network的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
