《算法周练4》A题解

题意：问的是给定比例的齿轮能否旋转.
思路：首先,如果这个齿轮不成环,那么肯定可以通过相邻的齿轮转动.
所以我们需要的是判断成环的时候是否也能够转动.
首先,我们dfs时进行赋值,通过这个比例来赋值,让起始点为1.0即可.
然后当我们第二次来到这个点时,它已经判断下成环后重新赋的值和之前赋的值是否一样,一样就说明可以一起旋转.
不一样说明无法旋转.
实现上,我们成环后判断的只是起始点,然后就不再继续dfs,保证了不会死循环.

Code:
double eps = 1e-6;
struct Node
{
    int to;
    double x,y;
};
vector<Node> G[1005];
double w[1005];
int vis[1005],f;
void dfs(int u,int fa)
{
    vis[u] = 1;
    for(int i=0;i<G[u].size();++i)
    {
        int y = G[u][i].to;
        double x = G[u][i].x,yy = G[u][i].y;
        if(y == fa) continue;
        if(!vis[y]) 
        {
            w[y] = w[u]*yy/x;
            dfs(y,fa);
        }
        else//成环后遍历到
        {
            double cal = w[u]*yy/x;
            if(abs(w[y]-cal) > eps)
            {
                f = 1;
                return ;
            }
        }
    }
}
int main()
{
    int t,ca = 0;sd(t);
    while(t--)
    {
        int n,m;sdd(n,m);
        for(int i=1;i<=n;++i) G[i].clear();
        while(m--)
        {
            int u,v;
            double x,y;
            cin >> u >> v >> x >> y;
            G[u].push_back(Node{v,x,y});
            G[v].push_back(Node{u,y,x});
        }
        f = 0;
        met0(vis);
        for(int i=1;i<=n;++i)
        {
            if(f) break;
            if(!vis[i])
            {
                w[i] = 1.0;
                dfs(i,0);
            }
        }
        if(f) printf("Case #%d: No\n",++ca);
        else printf("Case #%d: Yes\n",++ca);
    }
    system("pause");
    return 0;
}