立志用最少的代碼做最高效的表達(dá)

---

Description
現(xiàn)有一個(gè)傳動(dòng)系統(tǒng)，包含了N個(gè)組合齒輪和M個(gè)鏈條。每一個(gè)鏈條連接了兩個(gè)組合齒輪u和v，并提供了一個(gè)傳動(dòng)比x
: y。即如果只考慮這兩個(gè)組合齒輪，編號(hào)為u的齒輪轉(zhuǎn)動(dòng)x圈，編號(hào)為v的齒輪會(huì)轉(zhuǎn)動(dòng)y圈。傳動(dòng)比為正表示若編號(hào)
為u的齒輪順時(shí)針轉(zhuǎn)動(dòng)，則編號(hào)為v的齒輪也順時(shí)針轉(zhuǎn)動(dòng)。傳動(dòng)比為負(fù)表示若編號(hào)為u的齒輪順時(shí)針轉(zhuǎn)動(dòng)，則編號(hào)為v
的齒輪會(huì)逆時(shí)針轉(zhuǎn)動(dòng)。若不同鏈條的傳動(dòng)比不相容，則有些齒輪無法轉(zhuǎn)動(dòng)。我們希望知道，系統(tǒng)中的這Ｎ個(gè)組合齒
輪能否同時(shí)轉(zhuǎn)動(dòng)。

Input
有多組數(shù)據(jù)，第一行給定整數(shù)Ｔ，表示總的數(shù)據(jù)組數(shù)，之后依次給出Ｔ組數(shù)據(jù)。每一組數(shù)據(jù)的第一行給定整數(shù)Ｎ和
Ｍ，表示齒輪總數(shù)和鏈條總數(shù)。之后有Ｍ行，依次描述了每一個(gè)鏈條，其中每一行給定四個(gè)整數(shù)u，v，x和y，表示
只考慮這一組聯(lián)動(dòng)關(guān)系的情況下，編號(hào)為u的齒輪轉(zhuǎn)動(dòng)x圈，編號(hào)為v的齒輪會(huì)轉(zhuǎn)動(dòng)y圈。請注意，x為正整數(shù)，而y為
非零整數(shù)，但是y有可能為負(fù)數(shù)。
T<=32，N<=1000，M<=10000且x與y的絕對(duì)值均不超過100

Output
輸出T行，對(duì)應(yīng)每一組數(shù)據(jù)。首先應(yīng)該輸出標(biāo)識(shí)這是第幾組數(shù)據(jù)，參見樣例輸出。之后輸出判定結(jié)果，如果N個(gè)組合
齒輪可以同時(shí)正常運(yùn)行，則輸出Yes，否則輸出No。

Sample Input
2
3 3
1 2 3 5
2 3 5 -7
1 3 3 -7
3 3
1 2 3 5
2 3 5 -7
1 3 3 7

Sample Output
Case #1: Yes
Case #2: No

---

核心思路：帶權(quán)并查集模板

#include<bits/stdc++.h> #define N 1003 #define esp 1e-9 using namespace std; int n,m; int fa[N]; double sum[N]; int find(int x) { // 核心代碼if (fa[x]==x) return x;int t=find(fa[x]);sum[x]*=sum[fa[x]];fa[x]=t;return fa[x]; } int main() {int T; scanf("%d",&T);for (int t=1;t<=T;t++) {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) fa[i]=i,sum[i]=1;bool pd=false;for (int i=1;i<=m;i++) {int u,v,x,y; scanf("%d%d%d%d",&u,&v,&x,&y);int r1=find(u); int r2=find(v);if (r1!=r2) {fa[r2]=r1;sum[r2]*=sum[u]/sum[v]*(double)y/x;}else if (fabs((double)(sum[u]/sum[v])-((double)x/(double)y))>esp) {pd=true;}}printf("Case #%d: ",t);printf(pd ? "No\n" : "Yes\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【加权并查集】bzoj 4602 齿轮的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。