NC20583 [SDOI2016]齒輪
題目
題目描述
現有一個傳動系統，包含了N個組合齒輪和M個鏈條。每一個鏈條連接了兩個組合齒輪u和v，並提供了一個傳動比x : y。
即如果只考慮這兩個組合齒輪，編號為u的齒輪轉動x圈，編號為v的齒輪會轉動y圈。傳動比為正表示若編號為u的齒輪順時針轉動，則編號為v的齒輪也順時針轉動。傳動比為負表示若編號為u的齒輪順時針轉動，則編號為v的齒輪會逆時針轉動。若不同鏈條的傳動比不相容，則有些齒輪無法轉動。我們希望知道，系統中的這Ｎ個組合齒輪能否同時轉動。
輸入描述
有多組數據，第一行給定整數Ｔ，表示總的數據組數，之後依次給出Ｔ組數據。
每一組數據的第一行給定整數Ｎ和Ｍ，表示齒輪總數和鏈條總數。
之後有Ｍ行，依次描述了每一個鏈條，其中每一行給定四個整數u，v，x和y，表示只考慮這一組聯動關係的情況下，編號為u的齒輪轉動x圈，編號為v的齒輪會轉動y圈。
請注意，x為正整數，而y為非零整數，但是y有可能為負數。
T ≤ 32，N ≤ 1000，M ≤ 10000且x與y的絕對值均不超過100
輸出描述
輸出T行，對應每一組數據。首先應該輸出標識這是第幾組數據，參見樣例輸出。之後輸出判定結果，如果N個組合齒輪可以同時正常運行，則輸出Yes，否則輸出No。
示例1
輸入
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
輸出
Case #1: Yes
Case #2: No
題解
方法一
知識點：並查集。
用帶權並查集維護齒輪之間的關係，用權值表示根節點轉一圈，這個節點轉的圈數。
路徑壓縮，將父節點到根節點的權值乘以自己的權值。
集合合併，對於節點 \(x\) 和 \(y\) 以及其根節點 \(rx\) 和 \(ry\) ，將 \(rx\) 合併到 \(ry\) 需要得到 \(rx\) 的新權值，即得到 \(rx\) 和 \(ry\) 的傳動比，有：
\]
即四個齒輪的三個傳動比相乘得到 \(rx\) 和 \(ry\) 的傳動比再將 \(ry\) 圈數設為 \(1\) ，於是 \(w_{rx}\) 就等於 \(rx\) 與 \(ry\) 的傳動比乘以 \(ry\) 的圈數 \(1\) 。
如果新加關係的兩個點已經在一個關係集合中，那就檢驗是否合法：
\]
兩者傳動比是否相等，相等則合法。
注意精度問題，相等用小於誤差表示。
時間複雜度 \(O(n + m\log n)\)
空間複雜度 \(O(n)\)
方法二
知識點：DFS，圖論。
和並查集思路差不多，但建圖時要建無向圖，因為需要直到可能遍歷時走的是反向的。給起點權值賦為 \(1\) ，其他節點根據傳動比賦值，上一個節點乘以這個方向的傳動比的倒數的結果即是這個點實際轉多少圈。
如果遇到遍歷到一個訪問過的節點，那就判斷實際權值和目前算出來的權值是否相等。
時間複雜度 \(O(n+m)\)
空間複雜度 \(O(n+m)\)
程式碼
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
int fa[10007];
double w[10007];
int find(int x) {
if (fa[x] == x) return x;
int pre = fa[x];
fa[x] = find(fa[x]);
w[x] *= w[pre];
return fa[x];
}
bool merge(int x, int y, double r) {
int rx = find(x);
int ry = find(y);
if (rx == ry)
return abs(w[x] / w[y] - r) < 1e-6;
fa[rx] = ry;
w[rx] = 1 / w[x] * r * w[y];
return true;
}
bool solve() {
cin >> n >> m;
for (int i = 1;i <= n;i++) fa[i] = i, w[i] = 1;
bool flag = true;
for (int i = 0;i < m;i++) {
int u, v;
double x, y;
cin >> u >> v >> x >> y;
if (!flag) continue;
flag &= merge(u, v, x / y);
}
return flag;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1;i <= t;i++) {
cout << "Case #" << i << ": ";
if (!solve()) cout << "No" << '\n';
else cout << "Yes" << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
struct edge {
int to, nxt;
double w;
}e[10007 << 1];
int h[1007], cnt;
double vis[1007];
void add(int u, int v, double w) {
e[cnt].to = v;
e[cnt].w = w;
e[cnt].nxt = h[u];
h[u] = cnt++;
}
bool dfs(int u) {
for (int i = h[u];~i;i = e[i].nxt) {
int v = e[i].to;
if (vis[v]) {
if (abs(vis[v] - vis[u] / e[i].w) > 1e-6) return false;
}
else {
vis[v] = vis[u] / e[i].w;
if (!dfs(v)) return false;
}
}
return true;
}
bool solve() {
cin >> n >> m;
for (int i = 1;i <= n;i++) h[i] = -1, vis[i] = 0;
cnt = 0;
for (int i = 0;i < m;i++) {
int u, v;
double x, y;
cin >> u >> v >> x >> y;
add(u, v, x / y);
add(v, u, y / x);
}
vis[1] = 1;
return dfs(1);
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
for (int i = 1;i <= t;i++) {
cout << "Case #" << i << ": ";
if (!solve()) cout << "No" << '\n';
else cout << "Yes" << '\n';
}
return 0;
}
