Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

HR Spanning Tree Fraction ( 最優比例生成樹, Binary Search, Spanning Tree )

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解法: 裸的最優比例生成樹。 聽…

CFR 270 D. Design Tutorial: Inverse the Problem ( MST )

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…

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

UVA 1151 Buy or Build ( 枚舉 + 最小生成樹 )

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 10816 Travel in Desert ( 最小瓶頸生成樹 + 最短路徑 / 二分 + 最短路徑 )

UVa Online Judge 可以先依據邊的溫度求最小瓶頸生成樹,但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra,運行時間一模一樣。 #include <bits/stdc++.h> using namespace std; const int </bits/stdc++.h>…

UVA 10600 ACM Contest and Blackout ( 水題次小生成樹 )

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 10369 Arctic Network ( 水題最小瓶頸生成樹 )

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 12275 Sensor network ( 增量最小瓶頸生成樹 )

UVa Online Judge 和 UVA 1395 Slim Span是同一個問題,但測資加強 UVA 1395 Slim Span ( 水題最小瓶頸生成樹 ) - 0w1 因為允許18秒,所以試了看看哪裏可以做小優化,發現我每次加入一個邊都有重新排序,這是無意義的,做第一次就行了。但搬出來還是TLE。又…

UVA 1395 Slim Span ( 水題最小瓶頸生成樹 )

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. 迴路性質:任…