齿轮 HYSBZ - 4602 (DFS实现）
齿轮
题意：很好理解就不啰嗦了。 致谢：感谢队友小明。
题解：嗯，一开始想到的是并查集，后来，就先看了另一道题，xj写dfs和暴力，就卡死了。于是来补这题了，前向星建图题解：本题正解是考察并查集，不过这里就不说了，等到以后再说了。这题是用dfs来实现。Step1：很好想到就是把每一个齿轮搜索一下，（假设现在搜索u齿轮，可以往简单的方向想，即u转了一圈）然后把和u相连接的齿轮v判断一下，把v转的圈数存起来，因为接着要搜索v，判断与v相连的齿轮转的圈数（要存起来，后面会用到，step2里面，所以开个数组mo[]）。这个时候就需要一个vis[]数组，来记录这个点时候判断过了。 Step2：如果和u相连的v没有判断过，那么就标记一下，接着向下判断，但是如果要是判断过了，就说明可能形成了“互连”的样子，比如1-3,3-2,2-1，这样如果我们规定齿轮1转了一圈，那么齿轮3转的圈数可以计算完存起来，齿轮2转的圈数可以由齿轮3得到，那么开始判断与齿轮2相连的齿轮1时，因为齿轮1我们规定好了转一圈，那么用题目给的比值算一算，当前的齿轮2转的圈数合不合法就可以了，如果不合法，返回false，如果合法继续判断其他点。
Step3：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int v,x,y;
int next;
};
const int maxn = 20005;
struct node edge[maxn];
int vis[maxn];
double mov[maxn];
int head[maxn];
int cnt = 1, flag = 1;
void add(int u, int v, int x, int y) // 前向星建图
{
edge[cnt].v = v;
edge[cnt].x = x;
edge[cnt].y = y;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int x = edge[i].x;
int y = edge[i].y;
int v = edge[i].v;
if(vis[v] == 0) // 没有搜索过，就计算出来这个齿轮应该转的圈数
{
mov[v] = mov[u] / (double) x * (double) y;
vis[v] = 1;
dfs(v);
if(flag == 0) return ;
}
else //如果形成圈了，判断是否合法
{
if(abs(mov[u] * y - mov[v] * x) > 1e-7)
{
flag = 0;
return ;
}
}
}
}
int main()
{
int Case = 1,t,n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
cnt = 1;
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
for(int i = 1; i <= m; i ++)
{
int u,v,x,y;
scanf("%d%d%d%d",&u,&v,&x,&y);
add(u,v,x,y);
add(v,u,y,x);
}
vis[1] = 1;
mov[1] = 1.0;
flag = 1;
dfs(1);
if(flag) printf("Case #%d: Yes\n",Case ++);
else printf("Case #%d: No\n",Case ++);
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-11-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录