[NOI2001]食物鏈（並查集拓展域）&& [HAOI2006]旅行（Kruskal）
- 2019 年 11 月 2 日
- 筆記
題目描述
動物王國中有三類動物 A,B,C，這三類動物的食物鏈構成了有趣的環形。A 吃 B，B
吃 C，C 吃 A。
現有 N 個動物，以 1 － N 編號。每個動物都是 A,B,C 中的一種，但是我們並不知道
它到底是哪一種。
有人用兩種說法對這 N 個動物所構成的食物鏈關係進行描述：
第一種說法是“1 X Y”，表示 X 和 Y 是同類。
第二種說法是“2 X Y”，表示 X 吃 Y 。
此人對 N 個動物，用上述兩種說法，一句接一句地說出 K 句話，這 K 句話有的是真
的，有的是假的。當一句話滿足下列三條之一時，這句話就是假話，否則就是真話。
• 當前的話與前面的某些真的話衝突，就是假話
• 當前的話中 X 或 Y 比 N 大，就是假話
• 當前的話表示 X 吃 X，就是假話
你的任務是根據給定的 N 和 K 句話，輸出假話的總數。
輸入格式
從 eat.in 中輸入數據
第一行兩個整數，N，K，表示有 N 個動物，K 句話。
第二行開始每行一句話（按照題目要求，見樣例）
輸出格式
輸出到 eat.out 中
一行，一個整數，表示假話的總數。
emmmmm， 最近學了並查集， 並查集能維護連通性和傳遞性， 這道題假如單單用一個並查集來維護誰與誰是同類， 顯然無法判斷互相吃的情況， 那麼就容易想到用三個並查集去維護， 我們把每個動物x拆成3個節點， 分別表示同類域， 捕食域， 天敵域。假如x與y是同類， 那麼x， y捕食的物種和天敵都是一樣的， 把他們都合併。 而當x吃y時， 合併x的捕食域和y的同類域， x的同類域和y的天敵域， x的天敵域和y的捕食域。 在處理每句話之前， 首先要判斷這句話是否為真。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 5e4 + 100; const int MAXM = 3e3 + 10; const double eps = 1e-5; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') ff = -1; ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if (x == 0) { putchar('0'); return ; } if (x < 0) putchar('-'), x = -x; static T tot = 0, ch[30]; while (x) { ch[++tot] = x % 10 + '0'; x /= 10; } while (tot) putchar(ch[tot--]); } int n, m, ans, fa[MAXN * 3]; inline int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]); } int main() { // freopen("1.in", "r", stdin); read(n); read(m); for (int i = 1; i <= n * 3; ++i) fa[i] = i; while (m--) { // printf("ans = %dn", ans); int op, x, y; read(op); read(x); read(y); if (x > n || y > n) { ++ans; continue; }; if (op == 1) { if (get(x + n) == get(y) || get(x) == get(y + n)) ++ans; else { fa[get(x)] = get(y); fa[get(x + n)] = get(y + n); fa[get(x + n + n)] = get(y + n + n); } } else { if (get(x) == get(y) || get(x) == get(y + n)) ++ans; else { fa[get(x + n)] = get(y); fa[get(x + n + n)] = get(y + n); fa[get(x)] = get(y + n + n); } } } write(ans); return 0; }
View Code
題目描述
Z小鎮是一個景色宜人的地方，吸引來自各地的觀光客來此旅遊觀光。Z小鎮附近共有N個景點（編號為1,2,3,…,N），這些景點被M條道路連接着，所有道路都是雙向的，兩個景點之間可能有多條道路。也許是為了保護該地的旅遊資源，Z小鎮有個奇怪的規定，就是對於一條給定的公路Ri，任何在該公路上行駛的車輛速度必須為Vi。速度變化太快使得遊客們很不舒服，因此從一個景點前往另一個景點的時候，大家都希望選擇行使過程中最大速度和最小速度的比儘可能小的路線，也就是所謂最舒適的路線。
輸入格式
第一行包含兩個正整數，N和M。
接下來的M行每行包含三個正整數：x，y和v。表示景點x到景點y之間有一條雙向公路，車輛必須以速度v在該公路上行駛。
最後一行包含兩個正整數s，t，表示想知道從景點s到景點t最大最小速度比最小的路徑。s和t不可能相同。
輸出格式
如果景點s到景點t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。如果需要，輸出一個既約分數。
emmmmmm， 剛看到這到題的時候， 我就想到了最小差值生成樹， 這是我很早之前就做過的題了， 這個題算法上寫着並查集， 我當時就想Kruskal和並查集有什麼關係， 就專心致志的打我的dfs去了（我丟， 我好sb。。。），dfs的思路還是很容易想到的， 從s這個點開始枚舉每一條路徑， 把路徑上所有邊的最大最小值都記錄下來， 當到t這個點是時候比較就可以了， 然後我就神奇的MLE， 在一些神仙討論是數組開小還是爆內存的時候， 我默默地把dfs改成bfs， 結果依然MLE。 算了， 放棄這個暴力吧。 一位大佬提醒我一句， 把每條邊加進去， 判斷圖是否連通。 此時我好像幡然醒悟， 這不就是一個裸的Kruskal嘛， 然後， 我也就真的打了一個Kruskal， 我丟， 我是沒睡醒嘛, （其實確實有點瞌睡）， 稍作修改就A掉了。 可以說這是一道寫過的題了， 我甚至還hack正解， 在以後的學習中還是要學以致用啊。。。。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 5e5 + 100; const int MAXM = 3e3 + 10; const double eps = 1e-5; template < typename T > inline void read(T &x) { x = 0; T ff = 1, ch = getchar(); while (!isdigit(ch)) { if (ch == '-') ff = -1; ch = getchar(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } x *= ff; } template < typename T > inline void write(T x) { if (x == 0) { putchar('0'); return ; } if (x < 0) putchar('-'), x = -x; static T tot = 0, ch[30]; while (x) { ch[++tot] = x % 10 + '0'; x /= 10; } while (tot) putchar(ch[tot--]); } //bool cur1; int n, m, s, t, q1, q2, fa[MAXN]; struct tree { int x, y, v; bool operator < (const tree &a) const { return v < a.v; } }T[5100]; inline int gcd(int x, int y) { return x == 0 ? y : gcd(y % x, x); } inline int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); } inline void Kruskal(int ss) { for (int i = 1; i <= n; ++i) { fa[i] = i; } int maxx = -INF, minn = INF; for (int i = ss; i <= m; ++i) { int xx = get(T[i].x), yy = get(T[i].y); if (xx != yy) { fa[xx] = yy; maxx = max(maxx, T[i].v); minn = min(minn, T[i].v); } xx = get(s), yy = get(t); if (xx == yy) break; } int xx = get(s), yy = get(t); if (xx == yy) { if ((double) maxx / minn < (double) q1 / q2) q1 = maxx, q2 = minn; } } int main() { read(n), read(m); for (int i = 1; i <= m; ++i) { read(T[i].x); read(T[i].y); read(T[i].v); } read(s); read(t); sort(T + 1, T + m + 1); q1 = INF, q2 = 0; for (int i = 1; i <= m; ++i) Kruskal(i); if (q1 == INF) puts("IMPOSSIBLE"); else { int g = gcd(q1, q2); q1 /= g, q2 /= g; write(q1); if (q2 != 1) putchar('/'), write(q2); } return 0; }
View Code
