Spanning Tree
Problem - 609E - Codeforces題意： 給一張圖，分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約： N, M ≤ 2e5解法： 找出原圖的最小生成樹後，做倍增 LCA，同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹，直接輸出當前最小花費，否則…
Programming Problems and Competitions :: HackerRank題意： N 個點 M 個邊，第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹，使得 sum( a ) / sum( b ) 最大。制約： 2 ≤ N ≤ 1e5 N - 1≤ M ≤ 1e5 1 ≤ a[ i ], b[ i ] ≤ 100解法： 裸的最優比例生成樹。 聽…
Problem - D - Codeforces First we will have to take away apparently wrong cases, where dis[ i ][ i ] != 0 or dis[ i ][ j ] == 0 for i != j, or if dis[ i ][ j ] != dis[ j ][ i ]. We will find that we are willing to make a tree, so the short…
Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …
UVa Online Judge 先計算完全沒有用子網路集的生成樹，留下可能用到的 n - 1 條邊，再二進位枚舉子網路的可能子集。這麼做可以大大減少考慮不可能用到的邊。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = MAXN * MAXN / 2; c</bits/stdc++.h>…
UVa Online Judge 可以先依據邊的溫度求最小瓶頸生成樹，但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra，運行時間一模一樣。 #include <bits/stdc++.h> using namespace std; const int </bits/stdc++.h>…
UVa Online Judge 算出最小生成樹上每對最小瓶頸路徑就能 O( n * n ) 解決。 碎念：find() 函數忘了寫 return這個字= = #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; // 1 idx const int MAXC = 300 + 2; const int MAXM = MAXN * MAXN / 2; c</bits/stdc++.h>…
UVa Online Judge 取到排序後第 p - s + 1個最小的就可以了。 #include <bits/stdc++.h> using namespace std; const int MAXS = 100 + 2; const int MAXP = 500 + 2; const int MAXM = MAXP * MAXP / 2; int n, m; struct Edge{ int u, v; double w; Edge(){} Edge(int _u,</bits/stdc++.h>…
UVa Online Judge 和 UVA 1395 Slim Span是同一個問題，但測資加強 UVA 1395 Slim Span ( 水題最小瓶頸生成樹 ) - 0w1 因為允許18秒，所以試了看看哪裏可以做小優化，發現我每次加入一個邊都有重新排序，這是無意義的，做第一次就行了。但搬出來還是TLE。又…
UVa Online Judge 先將邊以邊權排序後，枚舉以哪個邊為最小值，用最小瓶頸生成樹的算法算出最小的最大值。複雜度 O( n * m lg m )。據說這題有進階版 UVa Online Judge UVA 12275 Sensor network - 0w1 #include <bits/stdc++.h> using namespace std; const int MAXN = 100</bits/stdc++.h>…
訓練指南裡提出了幾個經典的生成樹問題，我想做一點整理。 首先提出了最小生成樹有兩個性質： 1. 切割性質：任一個圖 G的子集 G'非空且不為 G本身，則其中一個端點在 G'裡，另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。 2. 迴路性質：任…
