Problem - 329B - Codeforces Let's think about all other trainers try to meet or wait us at the exit. Certainly if one is able to move to the exit before ( or on the same time ) we do, they will battle us. What if not? We will be able to av…

Problem - 377A - Codeforces 逆に連結成分を確保するという角度でやると簡単。 #include <bits/stdc++.h> using namespace std; const int MAXN = 500 + 5; const int MAXM = 500 + 5; const int dx[] = { 0, 1, 0, -1 }; const int dy[] = { 1, 0, -1, 0 }; int n, m, k, </bits/stdc++.h>…

Problem - C - Codeforces 細かいケースが多く、割と面倒くさい。 でもちゃんと考えてたら、実は簡単。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, d, h; void solve(){ if( n < h + 1 ) return (void)puts("-1"); // 一直線でやって</bits/stdc++.h>…

Problem - 300B - Codeforces 暴力でやるだけ。実装が下手。 つまらないミスで時間を溶かした。 #include <bits/stdc++.h> using namespace std; const int MAXN = 48 + 2; const int MAXM = MAXN * MAXN / 2; int n, m; vector< int > G[ MAXN ]; struct UnionFind{ int fa</bits/stdc++.h>…

Problem - C - Codeforces It's easy to see it is a complete graph, which means there exists exactly one path that could carry one from the start to the end. So the actual answer is quite simple, the maximum among the two shortest paths. Def…

Problem 1036. -- [ZJOI2008]树的统计Count このテクすごいね、猛練習しよう。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e4 + 4; const int MAXQ = 2e5 + 5; const int INF = 0x3f3f3f3f; int n; vector< int > es[ MAXN ], bes[ MAXN ]; int par[</bits/stdc++.h>…

http://sprout.tw/oj/pro/101/ 顯然就是二分圖。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 2 * MAXN; int n; vector< int > G[ MAXN ]; void init(){ for(int i = 0; i < n; ++i) G[ i ].clear(); } int col[ MAXN ]; bo</bits/stdc++.h>…

PEG Judge - IOI '03 Practice Task - Balancing Act The idea of a tree center, is a node in the tree that would minimize the maximum subtree size after it is removed. Carefully simulating it without recomputing will do alright. O( n ). #incl…

C: オレンジグラフ / Orange Graph - MUJIN プログラミングチャレンジ Programming Challenge | AtCoder It is already a well known fact that not to include any odd cycle is equivalent to having the graph bipartite. Since N is small ( ≤ 16 ), we …

把需要被覆蓋的節點押進該深度的節點表裡，之後依次選擇深度最深的為覆蓋的節點，用貪婪的思維找尋其 k級祖先設置伺服器。注意題目只要求葉節點覆蓋。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1000 + 3; int n, s, k; vector<int> G[MAXN]; vector<int> dept</int></int></bits/stdc++.h>…

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>…

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…

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