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…

UVa Online Judge 很明顯是一個類似次小生成樹的問題，因為只刪除一個邊，我們考慮一一枚舉要刪除的邊互相比較。將每個點對的最小瓶頸路徑預處理 O( n * n )，檢查刪除後的權值總和就能達到 O( 1 )。總複雜度 O( m lg m + n * n )。關於最小瓶頸路徑可以看這…

訓練指南裡提出了幾個經典的生成樹問題，我想做一點整理。 首先提出了最小生成樹有兩個性質： 1. 切割性質：任一個圖 G的子集 G'非空且不為 G本身，則其中一個端點在 G'裡，另一個端點在 G 的邊裡權值最小的必然會包含於 G的最小生成樹裡。 2. 迴路性質：任…

UVa Online Judge 由於順序無關，我們可以將每個操作獨立出來，令 dsum( u ) 為作用在 u 上的所有 d 權和，那麼對於一個邊 u -> v，它的最終邊權是 w( u, v ) + dsum( u ) - dsum( v )。由於題目要求最小值極大化，我們考慮二分搜尋，假設最小值的最大可能為…

UVa Online Judge 要求平均權值極大化，一個很常用的技巧是假設平均權值為 x，如果我們將全部的值減去 x以上的值，或全部減去 x - 1以下的值，前者和後者的差異在總和小於 0和大於 0。題目特別要求的是環，所以我們發現我們可以二分搜尋最接近正確答案的 x，…

UVa Online Judge 從終點逆推回去更新最小值。具體來說用 Priority First Search，尋找目前還沒用過的擁有最小值的節點來更新它所有可能的前驅點。打印路徑的時候只要反方向( 其實也就是順向 ) 檢查哪些點是可通行的，取其字典序最小慢慢遞進就行了。複雜度…

UVa Online Judge 用 Dijkstra 求一次從家裡到各個點的單源最短路徑，則所求是公司到家的路徑數，可走的有向邊只存在於滿足 DIjkstra 求出的 dis[ v ] v，很明顯是個 DAG，用 DP 隨便處理就行了。 #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const i</int,></bits/stdc++.h>…

UVa Online Judge 從起點和從終點各做一次單源最短路徑，並紀錄pre 陣列方便打印最短路徑。因為經濟線只能用一次，所以枚舉所有可以用的經濟線，還有一次完全不用經濟線的情況，比較哪個最好。時間複雜度 O( M lg N + K ) #include <bits/stdc++.h> using namespace std; ty</bits/stdc++.h>…

題目的圖論模型是要求將儘量少的點標記，使得刪除任意一點後每個聯通分量有至少一個被標記的點。 我們要發現一般來說標記在割點上不會比較好，而且在同一個點雙連通分量上標記兩個以上的點是無意義的。再說如果一個點雙連通分量含兩個以上的割點，我們可以不…

UVa Online Judge 用前綴和去想，若矩陣某個 ( i, j ) 為 +, 代表 pa( j ) - pa( i - 1 ) > 0, 同時意味著 pa( i - 1 ) ( j ) 建有向邊，最後的拓撲序就能是他們合法的大小關係。比較特別的是當pa( j ) - pa( i - 1 ) == 0 的時候，因為這代表 pa( j ) == pa…

UVa Online Judge 可以把顏色當作節點，則珠子就是節點之間的邊，題目要求就等價於問是否能用每個邊恰好一次構成一個迴路。這就是經典的尤拉迴路問題。 若滿足"所有點構成的圖聯通且不存在奇度數的節點"則必有尤拉迴路( 而且隨便走都是 )，而尤拉路徑除此之…

UVa Online Judge 一個大水題，先對火做BFS預處理每個格子發生火的最早時間，然後再搞人的就行了。注意會需要用到 ( t, x, y ) 三個變數一組的某種結構，以前都搞什麼雙重pair 真是太恐怖了，tuple我現在還不太會用。。寫完這題就想，我以後就像這樣子做吧。…