UVa Online Judge 是POJ 3352的進階版Biconnected Components - 0w1，差在不保證連通性。 題目給一個不保證連通的圖，要求將原本的邊隨意定向，求最少還要加入幾個有向邊才能使新圖強連通。先想能不能縮環，因為邊雙連通分量定向後一定可以是強連通分量，所…

UVa Online Judge 題目要求多筆詢問回答 a是否為 b的祖先。可以用時間戳記做樹壓平，只要 b所代表的區間[ in[ b ], out[ b ] ) 包含於 a的區間就說是。這題比較特別的是葉節點可以到很大，如果真的一一拜訪下去會 RE，所以必須不拜訪直接處理。除錯了好久才…

UVa Online Judge 正確率挺高的果然只是個裸二分圖判定。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; int n; vector<int> G[MAXN]; struct Bipartite{ int col[MAXN]; void init(){ memset( col, 0, sizeof(col) ); } bool canBip(int u){ for(in</int></bits/stdc++.h>…

UVa Online Judge 題目是很裸的最小瓶頸路徑，一般的做法是 O( n * n ) 生成樹相關問題 -- 訓練指南 - 0w1 但這題 n ≤ 50000，行不通，這時候就要使用比較難寫的最小瓶頸路徑，先進行一些預處理降到 O( n lg n ) 級別。注意求最小瓶頸路徑時我們用的 maxcost…