bzoj 4602 齿轮

Posted on | Views:

图的 $dfs$ 遍历.

  • 方向和速度显然可以分开判.
  • 方向就是判二分图.而对于速度,走过一条边,相对速度可以看做乘了一个比值.
  • 因为 $x,y\leq 100$ ,所以可以直接分解质因数,像染色那样做就可以了.
  • 时间复杂度 $O(25m)$ .

另外一种更优雅的方法是直接在模大质数意义下做乘除法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e4+10;
int ism[101],cnt=0,prime[101];
void init_prime()
{
	ism[1]=1;
	for(int i=2;i<=100;++i)
	{
		if(!ism[i])
			prime[++cnt]=i;
		for(int j=1;j<=cnt && prime[j]*i<=100;++j)
		{
			ism[prime[j]*i]=1;
			if(i%prime[j]==0)
				break;
		}
	}
}
int ecnt,head[MAXN];
struct edge
{
	int to,nx;
	int dir;
	int x,y;
}E[MAXN<<1];
void addedge(int u,int v,int x,int y)
{
	++ecnt;
	E[ecnt].to=v;
	E[ecnt].nx=head[u];
	E[ecnt].dir=(x*y<0)?-1:1;
	E[ecnt].x=abs(x);
	E[ecnt].y=abs(y);
	head[u]=ecnt;
}
int n,m;
int dir[MAXN],factor[MAXN][26];
void init()
{
	ecnt=0;
	memset(head,0,sizeof head);
	memset(dir,0,sizeof dir);
	memset(factor,0,sizeof factor);
}
int transfac[26];
void add(int x,int c)
{
	for(int i=1;i<=cnt && prime[i]<=x;++i)
		while(x%prime[i]==0)
		{
			x/=prime[i];
			transfac[i]+=c;
		}
}
bool dfs(int u)
{
	bool flag=true;
	for(int i=head[u];i && flag;i=E[i].nx)
	{
		int v=E[i].to;
		memset(transfac,0,sizeof transfac);
		add(E[i].y,1);
		add(E[i].x,-1);
		if(dir[v])
		{
			if(dir[u]*E[i].dir!=dir[v])
				return false;
			for(int i=1;i<=25;++i)
				if(factor[u][i]+transfac[i]!=factor[v][i])
					return false;
		}
		else
		{
			dir[v]=dir[u]*E[i].dir;
			for(int i=1;i<=25;++i)
				factor[v][i]=factor[u][i]+transfac[i];
			flag&=dfs(v);
		}
	}
	return flag;
}
int main()
{
	init_prime();
	int T=read();
	for(int casenum=1;casenum<=T;++casenum)
	{
		init();
		n=read(),m=read();
		for(int i=1;i<=m;++i)
		{
			int u=read(),v=read(),x=read(),y=read();
			addedge(u,v,x,y);
			addedge(v,u,y,x);
		}
		bool flag=true;
		for(int i=1;i<=n && flag;++i)
			if(!dir[i])
			{
				dir[i]=1;
				flag&=dfs(i);
			}	
		if(flag)
			printf("Case #%d: Yes\n",casenum);
		else
			printf("Case #%d: No\n",casenum);
	}
	return 0;
}