P3247 [HNOI2016]最小公倍数

    • 50通过
    • 281提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 并查集 排序 枚举,暴力 2016 湖南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms-4000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一张N个顶点M条边的无向图(顶点编号为1,2,...,n),每条边上带有权值。所有权值都可以分解成$2^a*3^b$ 的形式。

    现在有q个询问,每次询问给定四个参数u、v、a和b,请你求出是否存在一条顶点u到v之间的路径,使得路径依次经过的边上的权值的最小公倍数为$2^a*3^b$ 。

    注意:路径可以不是简单路径。下面是一些可能有用的定义:最小公倍数:K个数a1,a2,...,ak的最小公倍数是能被每个ai整除的最小正整数。

    路径:路径P:P1,P2,...,Pk是顶点序列,满足对于任意1<=i<k,节点Pi和Pi+1之间都有边相连。简单路径:如果路径P:P1,P2,...,Pk中,对于任意$1\le s\ne t\le k$ 都有$Ps\ne Pt$ ,那么称路径为简单路径。

    输入输出格式

    输入格式:

    输入文件的第一行包含两个整数N和M,分别代表图的顶点数和边数。接下来M行,每行包含四个整数u、v、a、b代表一条顶点u和v之间、权值为$2^a*3^b$ 的边。接下来一行包含一个整数q,代表询问数。接下来q行,每行包含四个整数u、v、a和b,代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9

    输出格式:

    对于每次询问,如果存在满足条件的路径,则输出一行Yes,否则输出一行 No(注意:第一个字母大写,其余字母小写) 。

    输入输出样例

    输入样例#1: 复制
    4 5
    1 2 1 3
    1 3 1 2
    1 4 2 1
    2 4 3 2
    3 4 2 2
    5
    1 4 3 3
    4 2 2 3
    1 3 2 2
    2 3 2 2
    1 3 4 4
    输出样例#1: 复制
    Yes 
    Yes 
    Yes 
    No 
    No
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。