[SDOI2016]齿轮
[SDOI2016]齿轮
http://www.nowcoder.com/questionTerminal/f8bea9a0967e4edc9da7816c657d0699
题目大意：
有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();
}
} 
腾讯成长空间 6065人发布