题目描述
给出一张n个点m条边的有向图，每条边 (u,v,x,y) 描述了 u 的点权乘 x 等于 v 的点权乘 y （点权可以为负）。问：是否存在满足条件的图。
输入
有多组数据，第一行给定整数Ｔ，表示总的数据组数，之后依次给出Ｔ组数据。每一组数据的第一行给定整数Ｎ和
Ｍ，表示齿轮总数和链条总数。之后有Ｍ行，依次描述了每一个链条，其中每一行给定四个整数u，v，x和y，表示
只考虑这一组联动关系的情况下，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。请注意，x为正整数，而y为
非零整数，但是y有可能为负数。
T<=32，N<=1000，M<=10000且x与y的绝对值均不超过100
输出
输出T行，对应每一组数据。首先应该输出标识这是第几组数据，参见样例输出。之后输出判定结果，如果N个组合
齿轮可以同时正常运行，则输出Yes，否则输出No。
样例输入
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
题解
BFS
显然固定一个点，通过条件判断出其它点是否是它的固定倍数即可。添加双向边，维护每个点是某个点的多少倍，BFS验证。
但是有一个问题：倍数关系是指数级的，因此需要取对数。
但是有一个问题：边权有负数，因此需要维护符号和绝对值的对数。
但是有一个问题：有精度误差，因此需要设eps为$10^{-6}$。
时间复杂度$O(T(n+m))$
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#define N 1010
#define M 20010
using namespace std;
queue<int> q;
int head[N] , to[M] , vp[M] , next[M] , cnt , vis[N] , flag[N];
double val[M] , dis[N];
void add(int x , int y , double z , int p)
{
to[++cnt] = y , val[cnt] = z , vp[cnt] = p , next[cnt] = head[x] , head[x] = cnt;
}
bool judge(int p)
{
int i , x;
while(!q.empty()) q.pop();
vis[p] = 1 , q.push(p);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
if(!vis[to[i]]) vis[to[i]] = 1 , flag[to[i]] = flag[x] ^ vp[i] , dis[to[i]] = dis[x] + val[i] , q.push(to[i]);
else if(flag[to[i]] != (flag[x] ^ vp[i]) || fabs(dis[to[i]] - dis[x] - val[i]) > 1e-6) return 0;
}
}
return 1;
}
int main()
{
int T , Case;
scanf("%d" , &T);
for(Case = 1 ; Case <= T ; Case ++ )
{
memset(head , 0 , sizeof(head)) , memset(vis , 0 , sizeof(vis)) , cnt = 0;
int n , m , x , y , i , a , b;
scanf("%d%d" , &n , &m);
while(m -- )
{
scanf("%d%d%d%d" , &x , &y , &a , &b);
if(b > 0) add(x , y , log(b) - log(a) , 0) , add(y , x , log(a) - log(b) , 0);
else add(x , y , log(-b) - log(a) , 1) , add(y , x , log(a) - log(-b) , 1);
}
for(i = 1 ; i <= n ; i ++ )
if(!vis[i])
if(!judge(i))
break;
printf("Case #%d: " , Case);
if(i > n) puts("Yes");
else puts("No");
}
return 0;
}