传递闭包+二进制位运算+floyd(poj2570)
2024-10-02 04:20:42
DescriptionFiber Network
Time
Limit: 1000MSMemory Limit: 65536K Total Submissions: 3125 Accepted: 1436 Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes.Input
Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.Output
After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.Sample Input3
1 2 abc
2 3 ad
1 3 b
3 1 de
0 0
1 3
2 1
3 2
0 0
2
1 2 z
0 0
1 2
2 1
0 0
0Sample Output
ab
d
- z
-题意:给出n个点,然后给出边a,b ,str代表str中的这些字母可以保证a到b的联通,然后有多组询问u和v,问u到v可以由那些字母保证连通性,若没有输出-
分析:一共26个字母可以使用位运算,g[a][b]代表那些可以联通,用传递闭包即可#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"queue"
#include"algorithm"
#include"string.h"
#include"string"
#include"math.h"
#include"vector"
#include"stack"
#include"map"
#define eps 1e-8
#define inf 0x3f3f3f3f
#define M 250
using namespace std;
int g[M][M],vis[M];
char str[M];
int main()
{
int n,i,a,b,c,j,k,kk=0;
while(scanf("%d",&n),n)
{
memset(g,0,sizeof(g));
memset(vis,0,sizeof(vis));
while(scanf("%d%d",&a,&b),a||b)
{
scanf("%s",str);
for(i=0;str[i]!='\0';i++)
{
c=str[i]-'a';
g[a][b]|=(1<<c);
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
g[i][j]|=(g[i][k]&g[k][j]);
}
}
}
if(kk)
printf("\n");
kk++;
while(scanf("%d%d",&a,&b),a||b)
{
int flag=0;
for(i=0;i<26;i++)
{
if(g[a][b]&(1<<i))
{
printf("%c",i+'a');
flag++;
}
}
if(flag)
printf("\n");
else
printf("-\n");
}
}
return 0;
}
最新文章
- hdu4059 The Boss on Mars(差分+容斥原理)
- 一次Mysql 死锁事故
- sDashboard:简单的,轻量级的 jQuery 仪表板插件
- vmware, failed to lock the file
- 关于Eclipse部署openfire3.8.2源码的体会
- discuz ucenter通信失败
- Redis数据持久化之RDB持久化
- [Everyday Mathematics]20150203
- angular中ueditor插件的使用
- Cygwin的安装及在Android jni中的简单使用举例
- bently addin 二次开发学习
- 使用JavaScript验证用户输入的是否为正整数
- 24种java设计模式总结和目录
- JS 时间函数 / 格式化时间戳
- asp.net 网页拉伸 到300%不变形方法一
- easyloader分析与使用
- 使用Vuex打开log功能
- windows开通https服务
- java线程(上)Thread和Runnable的区别
- 没有Reduce的MapReduce(一)