A6860. 「SDOI2016」齿轮
编程题
提高+/省选-
知识点
题目描述
现有一个传动系统，包含了 $N$ 个组合齿轮和 $M$ 个链条。每一个链条连接了两个组合齿轮 $u$ 和 $v$，并提供了一个传动比 $x:y$。即如果只考虑这两个组合齿轮，编号为 $u$ 的齿轮转动 $x$ 圈，编号为 $v$ 的齿轮会转动 $y$ 圈。传动比为正表示若编号为 $u$ 的齿轮顺时针转动，则编号为 $v$ 的齿轮也顺时针转动。传动比为负表示若编号为 $u$ 的齿轮顺时针转动，则编号为 $v$ 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希望知道，系统中的这 $N$ 个组合齿轮能否同时转动。
输入格式
有多组数据，第一行给定整数 $T$，表示总的数据组数，之后依次给出 $T$ 组数据。
每一组数据的第一行给定整数 $N$ 和 $M$，表示齿轮总数和链条总数。
之后有 $M$ 行，依次描述了每一个链条，其中每一行给定四个整数 $u$，$v$，$x$ 和 $y$，表示只考虑这一组联动关系的情况下，编号为 $u$ 的齿轮转动 $x$ 圈，编号为 $v$ 的齿轮会转动 $y$ 圈。请注意，$x$ 为正整数，而 $y$ 为非零整数，但是 $y$ 有可能为负数。
每一组数据的第一行给定整数 $N$ 和 $M$，表示齿轮总数和链条总数。
之后有 $M$ 行，依次描述了每一个链条，其中每一行给定四个整数 $u$，$v$，$x$ 和 $y$，表示只考虑这一组联动关系的情况下，编号为 $u$ 的齿轮转动 $x$ 圈，编号为 $v$ 的齿轮会转动 $y$ 圈。请注意，$x$ 为正整数，而 $y$ 为非零整数，但是 $y$ 有可能为负数。
输出格式
输出 $T$ 行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果 $N$ 个组合齿轮可以同时正常运行，则输出 `
Yes，否则输出 No`。输入输出样例
输入 #1
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
输出 #1
Case #1: Yes Case #2: No
说明/提示
对于所有的数据，$T \leq 32, \ N \leq 1000, \ M \leq10000, \ |x|, |y| \leq 100$。