齿轮 HYSBZ - 4602 (DFS实现）

齿轮

HYSBZ - 4602

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;

}