POJ2570 二进制,位运算,Floyd
二进制 运算 Floyd
2023-09-11 14:13:59 时间
题意:
给你一个有向图,两点之间有多种连接方式,然后每次询问都问你点A,B之间有哪些方式可以到达,每个小字母是一个方式.
思路:
给你一个有向图,两点之间有多种连接方式,然后每次询问都问你点A,B之间有哪些方式可以到达,每个小字母是一个方式.
思路:
很巧妙的位运算和Floyd应用,借助Floyd的更新过程,去更新任意两组边组合起来的长边,如 map[i][j] 是由 map[i][k] 和 map[k]][j]接起来的,更新方式很容易理解,是map[i][j] = map[i][j] | (map[i][k] & map[k][j]),每条边的状态都转化成2进制就行了。
#include<stdio.h>
#include<string.h>
int map[205][205];
int Pow(int n)
{
int p = 1;
for(int i = 1 ;i <= n ;i ++)
p *= 2;
return p;
}
int main ()
{
int n;
int a ,b ,l ,i ,j ,k;
char str[100];
while(~scanf("%d" ,&n) && n)
{
memset(map ,0 ,sizeof(map));
while(scanf("%d %d" ,&a ,&b) && a + b)
{
scanf("%s" ,str);
l = strlen(str);
for(i = 0 ;i < l ;i ++)
map[a][b] += Pow(str[i] - 'a');
}
for(k = 1 ;k <= n ;k ++)
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
map[i][j] = map[i][j] | (map[i][k] & map[k][j]);
while(scanf("%d %d" ,&a ,&b) && a + b)
{
int mk = 0;
for(i = 0 ;i < 26 ;i ++)
{
if(map[a][b] & Pow(i))
{
printf("%c" ,'a' + i);
mk = 1;
}
}
if(!mk) printf("-");
printf("\n");
}
printf("\n");
}
return 0;
}
相关文章
- Java实现 LeetCode 693 交替位二进制数(位运算)
- Java实现 蓝桥杯VIP 算法训练 递归求二进制表示位数
- 二进制日志BINARY LOG清理
- Centos7 k8s v1.5.2二进制部署安装-交付jenkins到k8s集群
- LeetCode-面试题 05.02. 二进制数转字符串【数学,字符串,位运算】
- atitit.二进制数据无损转字符串网络传输
- js 二进制 十进制 十六进制 buffer 字节数组 字符串 相互转换
- 一张图:勾画二进制和汇编和C及内存地址及数据顺序
- 基于二进制粒子群算法的背包问题求解- 附代码
- 【Android 安装包优化】资源混淆 ( resources.arsc 资源映射表混淆 | resources.arsc 资源映射表二进制格式分析 | 混淆全局字符串池和资源名称字符串池 )
- 二进制原码 反码 补码详解
- 文本文件与二进制文件理解
- 二进制代码运算规律是逢二进一
- 微信小程序如何将二进制的数据流转为PNG图片
- 计算机组成原理 二进制数的运算