云空间搭建网站/南安网站建设

题意：        

       有一个有向图,对于有向图的每条边上有一个公司名字的集合,代表该集合内的公司能提供该边的连通服务.现在我们给你q个查询.对于每个查询a和b,你要回答有哪些公司能提供从a到b的通路服务.。

思路：题意就是给你一个起点a,终点b。然后让你输出a->b路上的公共字符。这算是一种集合关系，相同线路取交集，不同线路取并集，显然用二进制存储更加方便，26个字符对应着二进制中 0 ~25位。压缩完边之后，用floyed传递一下，最后用lowbit不断出最后一位就可以了。

AC Code：

#include<iostream>
#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<sstream>
using namespace std;
int w[205][205];
int n,m;
map<int,int > st;
void floyed()
{for(int k = 1;k <= n; ++k)for(int i = 1;i <= n; ++i)for(int j = 1;j <= n; ++j)w[i][j] = w[i][j] |  (w[i][k] & w[k][j]);
}
int lowbit(int x)
{return x&(-x);
}
int main()
{//freopen("input.txt","r",stdin);for(int i = 'a' - 'a';i<='z' - 'a';++i)//打表，预处理lowbit对应1在哪一位{st[1<<i] = i;}string s1,s2;int f,t;while(cin>>n&&n){memset(w,0,sizeof(w));while(cin>>f>>t&&f+t){cin>>s1;stringstream ss(s1);char c;while(ss>>c){w[f][t] |= 1<<(c - 'a');//将边压缩}}floyed();while(cin>>f>>t&&f+t){int tmp = w[f][t];if(tmp==0) cout<<'-'<<endl;else {while(tmp){int idx = lowbit(tmp);cout<<char('a' + st[idx]);tmp -= idx;}puts("");}}cout<<endl;}
}