【bzoj4602】[Sdoi2016]齿轮 BFS

题目描述

给出一张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;

}

巴特西

【bzoj4602】[Sdoi2016]齿轮 BFS

最新文章

热门文章