#P4602. [Sdoi2016]齿轮

    ID: 1772 传统题 1000ms 512MiB 尝试: 1441 已通过: 421 难度: 6 上传者: 标签>难度分类提高枚举与搜索广度优先搜索数据结构势能维护数论试除法分解质因数CF1900

[Sdoi2016]齿轮

[SDOI2016] 齿轮

题目描述

一个传动系统有 NN 个组合齿轮和 MM 条链条。每条链条连接编号为 u,vu,v 的两个齿轮,给定传动比 x:yx:y。当齿轮 uu 转动 xx 圈时,齿轮 vv 应转动 yy 圈。yy 为正表示两齿轮转动方向相同,为负表示方向相反。

判断是否存在一种使所有齿轮同时转动、并满足所有链条传动比的方式。每个齿轮的转速都必须非零。

输入格式

第一行一个整数 TT,表示测试组数。每组第一行两个整数 N,MN,M。随后 MM 行,每行四个整数 u,v,x,yu,v,x,y,描述一条链条及其传动比。齿轮编号为 11 到 NN。

输出格式

每组输出一行。第 ii 组若能使所有齿轮同时转动,输出 Case #i: Yes,否则输出 Case #i: No。将 i 替换为组号,从 11 开始。

2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7
Case #1: Yes
Case #2: No

数据范围

1≤T≤321\le T\le32,1≤N≤10001\le N\le1000,0≤M≤100000\le M\le10000,1≤x≤1001\le x\le100,1≤∣y∣≤1001\le |y|\le100,1≤u,v≤N1\le u,v\le N。

对于 30%30\% 的数据,N≤10N\le10、M≤20M\le20、x,∣y∣≤18x,|y|\le18。