[SDOI2016]齿轮

题目大意：

有N个轮子，每个轮子有一个属性（转速）。轮子之间M个二元关系，每个关系有4个属性u，v，x，y。表示轮子u和v的转速比值为x：y。问：这m个关系是否相容。（即可以同时满足）。
一共T组询问T ≤ 32，N ≤ 1000，M ≤ 10000且x与y的绝对值均不超过10。

分析：

设第i个轮子的转速为。若:已知且:已知，那么:为一可计算的确定的值。若此时题目中给出与的比值且这个比值与求出来的比值不相等，就可以说明不相容。
为了实现这个判断，我弄了一个fr[]数组，来判断节点是否“自由”（就是说转速是不是任意的，如果是就把这个节点的转速置为1。然后和它相连的节点的转速都可以计算了），注意同一个一个联通块不能分开处理。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> P;
const int INF=0x3f3f3f3f;
const LL LINF=0x3f3f3f3f3f3f;
const int MAX_N=1000+20;
const LL MOD=1e9+7;
struct Node{
    int v;
    double p;
    Node(int a,double b):v(a),p(b){};
};
vector<Node> V[MAX_N];
set<int>S;
int fr[MAX_N];
int vis[MAX_N];
double val[MAX_N];
int T;
int flag;
int N,M;
int cnt=1;
void init(){
    for(int i=1;i<=N;i++){
        fr[i]=1;
        V[i].clear();
        vis[i]=0;
        S.insert(i);
    }
    flag=1;
}
void input(){

    int a,b;
    double c,d;
    cin>>N>>M;
    init();
    while(M--){
        cin>>a>>b>>c>>d;
        V[a].push_back(Node(b,d/c));
        V[b].push_back(Node(a,c/d));
    }
}
void dfs(int e){
    vis[e]=1;
    S.erase(e);
    int len=V[e].size();
    for(int i=0;i<len;i++){
        if(!fr[V[e][i].v]){
            //cout<<V[e][i].v<<endl;
            if(val[V[e][i].v]-V[e][i].p*val[e]>1e-6){
                flag=0;
                return;
            }
        }
        else{
            val[V[e][i].v]=val[e]*V[e][i].p;
            fr[V[e][i].v]=0;
        }
        if(!vis[V[e][i].v]){
            dfs(V[e][i].v);
        }
    }
    if(flag==0) return;

}
void solve(){
    cout<<"Case #"<<cnt<<": ";
    cnt++;
    while(!S.empty()){
        int e=*S.begin();
        fr[e]=0;
        val[e]=1;
        vis[e]=1;
        dfs(e);
        if(!flag){
            cout<<"No"<<endl;
            return;
        }
    }
    cout<<"Yes"<<endl;
}
int main(){
    //freopen("1.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        input();
        solve();
    }

}