Subscribed unsubscribe Subscribe Subscribe

0w1

Graph

CFR 806 D. Perishable Roads ( Shortest Path, Graph )

Problem - D - Codeforces題意: 有 N 個城市,每對城市之間存在一個雙向路徑,每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x,問一種方法,使得每個點對外都只留下一個有向邊,使得所有城市都會到達城市 …

CSAcademy 25. Zone Capture ( BCC )

Round #25 (Div. 2 only)題意: 給一個 01 矩陣 A[ N ][ M ]。你可以選擇一個 0 轉為 1,轉換後,所有不和任意一個邊界的 0 屬於同一個連通塊 ( 上下左右,且兩者皆 0 視為相鄰 ) 的所有 0 都會轉為 1。問最多可以有多少 1。制約: 1 ≤ N, M ≤ 1000解法: 將…

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

Problem - C - Codeforces題意: 給一個圖,要求放 K 個機器人並給出每個機器人的路徑,路徑長至多為 ceil( 2 * N / K ),使得所有節點都被至少一個機器人拜訪過。資料規模: N, M ≤ 2e5解法: 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS,…

CFR 228 E. The Road to Berland is Paved With Good Intentions ( 2SAT )

Problem - 228E - Codeforces題意: 給 N 個點 M 條邊,邊有邊權 0 或 1。每次操作選取一個點,將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1,若有則輸出方案。資料規模: N ≤ 100 解法: 考慮每個邊,其實只能被兩端點…

CFR 11 D. A Simple Task ( DP, Bitmask, Hamiltonian Walk )

Problem - 11D - Codeforces題意: 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模: N ≤ 19 TL: 2000 ms解法: 考慮一個環,選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊,假設原本是 abcd 這樣的環,那其實可以用點的集合和…

CFR 389 D. Fox and Minimal path ( Binary Enumeration )

Problem - D - Codeforces題意: 給 K,求一個無向圖鄰接矩陣,使得節點 1 到節點 2 的最短路徑恰有 K 個。資料規模: 1 ≤ K ≤ 1e9 輸出的圖的節點數 ≤ 1000解法: 考慮二進制枚舉,需要 *2 就往右連一個菱形,需要 +1 就從節點 1 連到當前的終點。 #include <bits/stdc++.h></bits/stdc++.h>…

POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…

CFR 645 D. Robot Rapping Results Report ( Graph, TopoSort, Binary Search )

Problem - 645D - Codeforces題意: 有 N 個機器人打鬥,機器人之間勝負是依戰鬥力的大小關係定的,而所有機器人的戰鬥力相異。依順序給機器人編號 u[ i ], v[ i ],表示編號 u[ i ] 的機器人戰鬥力比 v[ i ] 的機器人高。求第幾個資訊開始能確定所有機器人…

ARC 065 D - 連結 ( Ad hoc )

D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意: 給相同節點數的兩個圖,對於每個點,求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模: 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…

CFR 742 E. Arpa’s overnight party and Mehrdad’s silent entering ( Bicoloring / Random )

Problem - E - Codeforces題意: 在一個圓桌上吃飯,有兩種飯,希望每連續三個人,都一定有一個人吃不一樣的東西。每個人都有一個唯一對應的伴侶,而伴侶之間也規定不能吃一樣的東西。求合法分配的結果。若無法分配,輸出 -1。資料規模: 情侶對數 1 ≤ n ≤ 1…

CFR 147 B. Smile House ( Binary Search, Fast Matrix Multiplication, DP, Binary Enumeration )

Problem - B - Codeforces題意: 給一個圖,邊用四個值表示,( x, y, Cxy, Cyx ),代表 x 至 y 長度是 Cxy,y 至 x 長度是 Cyx。求是否存在一個正環,若存在則輸出最小環的長度。資料規模: 節點數 1 ≤ N ≤ 300 邊數 0 ≤ M ≤ N * ( N - 1 ) / 2 權值 -1e4 ≤ …

CFR 459 E. Pashmak and Graph ( DP )

Problem - E - Codeforces題意: 給一張帶權有向圖。求最長路徑長度,路徑滿足邊權嚴格遞增。數據範圍: 節點 2 ≤ N ≤ 3e5 邊數 1 ≤ M ≤ min( N * ( N - 1 ) / 2, 3e5 ) 邊權 1 ≤ W[ i ] ≤ 1e5 保證無自環,無重邊。解法: 先考慮將邊權小至大排序。此時發現…

CFR 349 D. World Tour ( Graph )

Problem - D - Codeforces Edges are all weighted 1, so we can apply BFS for single source shortest path, for each node as source. This allows us to get all pairwise distances in O( n ^ 2 ). Since we are to find the maximum distance of path …

GCJ 2016 R1A pC. BFFs ( Graph Adhoc )

Dashboard - Round 1A 2016 - Google Code Jam There are two possible ways to form a maximum cycle: 1. Sum up for each pair ( u, v ) that share bidirectional edges, length of chain that starts with u, and v, such like f[ f[ .. f[ v ] ] ] u ->…

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…

CFR 25 C. Roads in Berland ( Floyd Warshall )

Problem - 25C - Codeforces 先做完一次MSSP之後,對於每個動態操作可以直接詢問每個兩端,是否用了這條邊之後會更好。 注意題目是說額外新增路,所以是不一定要取的。 #include <bits/stdc++.h> using namespace std; const int MAXN = 300 + 3; const int MAXK = 300 + 3;</bits/stdc++.h>…

CFR 295 1B. Greg and Graph ( DP = Floyd Warshall + Reverse Thinking )

Problem - B - Codeforces 如果順著做,逐一破壞。。嗯,看到逐一破壞就可以開始想反著觀察就是逐一增加了。 因為問題是Multiple Source Shortest Path,所以可以馬上想到Floyd Warshall演算法了。 想起以前學長和我提過,為什麼三層迴圈的中繼點要在最外圈…

CFR 20 C. Dijkstra? ( Dijkstra )

Problem - 20C - Codeforces 根本裸題。。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; const int MAXW = 1e6 + 6; typedef long long ll; typedef pair< int, int > pii; typedef pair< ll, int > pli; int n, m;</bits/stdc++.h>…

CFR 238 1C. World Eater Brothers ( Tree DP )

Problem - C - Codeforces 基本上和這道題是相同的概念 CFR 219 D. Choosing Capital for Treeland ( Tree DP ) - 0w1 不過這題的要點在於意識到樹的唯一路徑性質使得選擇任一條邊後兩端一定可以各自形成一顆子樹。因此只要枚舉所有邊,再各自處理所有情況就…

CFR 219 D. Choosing Capital for Treeland ( Tree DP )

Problem - D - Codeforces 搞了很久才弄出來。。首先要分成兩種邊,一種是順向邊,輸入給定的邊,一種是逆向邊,就是要經過反轉才能用的邊。這麼一來,我們可以先透過一次深搜得到隨便一個點當根的時候的花費。顯然我們不能暴力對所有根重新計算,但我們可以…

CFR 245 1A. Xor-tree ( Greedy + DFS )

Problem - 429A - Codeforces It is obvious that if all nodes above are cleared and the current node is not the target, it has to be flipped. It is never better to flip its ancestors, for it will cost extra for nothing. We don't have to go d…

GCJ 2014 R1A pB. Full Binary Tree ( DFS )

Dashboard - Round 1A 2014 - Google Code Jam 題目中一個合法的完全樹的定義是,所有節點的子節點數為0或2。要求的是移除最少點使得給定的樹成為完全樹。因為數據範圍小,可以考慮枚舉每個節點作為根,再做一次線性的深搜處理。根據定義可以得到遞迴函數,…

CFR 129 C. Statues ( BFS )

Problem - C - Codeforces WA了一次,以為只會原地待著,或往上或往右或往右上移動。仔細想想,這全部方向都得考慮。 #include <bits/stdc++.h> using namespace std; const int MAXH = 8 + 2; const int MAXW = 8 + 2; typedef pair< int, int > pii; char G[ MAXH ][ MAXW</bits/stdc++.h>…

CFR 129 B. Students and Shoelaces ( DFS )

Problem - B - Codeforces 把度數和邊的變量維護好就很簡單。 #include <bits/stdc++.h> using namespace std; const int MAXN = 100 + 2; const int MAXM = MAXN * MAXN / 2; int n, m; vector< int > G[ MAXN ]; int deg[ MAXN ], d_deg[ MAXN ]; void solve(){ int cnt =</bits/stdc++.h>…

CFR 131 D. Subway ( 水母圖 DFS )

Problem - 131D - Codeforces n個點 n條邊保證聯通,俗稱的水母圖。題目求的是每個點與環的距離,所以用一次 dfs求環,利用 next數組就能夠紀錄並判環。最後再把所有環裡的點拿去做bfs求距離。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e3 + 3; in</bits/stdc++.h>…

CFR 659 E. New Reform ( DFS )

Problem - E - Codeforces 点が全て連結する場合を考えて、辺の数だけ degree = 1の点の数ができるとわかる。つまり、連結成分それぞれについてそれを求めればいい。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXM = 1e5 + 5; t</bits/stdc++.h>…

CFR 404 C. Restore Graph ( Adhoc )

Problem - 404C - Codeforces The vertex i with dis[ i ] = 0 will be the origin, and if it doesn't exist, or multiple 0 distance vertices exist, there will be no solution. Otherwise iterate through all distances from smaller to larger and ex…

CFR 330 E. Graph Reconstruction ( Random Search )

Problem - E - Codeforces The deterministic solution for this problem is quite difficult. However, it is easy to come up with a randomised algorithm. There are primarily 2 types of randomised algorithms, Monte Carlo that runs in a certain t…

CFR 330 B. Road Construction ( Graph Adhoc )

Problem - 330B - Codeforces There are n vertices and at most n / 2 - 1 edges. Easy to see that there will be at least one vertex with 0 degree. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 3; const int MAXM = MAXN / 2; int n, m; i</bits/stdc++.h>…

CFR 329 1B. Biridian Forest ( Shortest Path )

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…

CFR 377 1A. Maze ( BFS + Reverse Thinking )

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

CFR 658 C. Bear and Forgotten Tree 3 ( Adhoc Tree )

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

CFR 300 B. Coach ( DFS )

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

CFR 602 C. The Two Routes ( Floyd Warshall )

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…

BZOJ 1036 树的统计 ( 樹平方分割 )

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

TOJ 101 哪裡有卦,哪裡就有源 ( 水題二分圖 )

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

IOI '03 Practice Task - Balancing Act ( Easy Tree center )

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…

ATC MUJIN C. Orange Graph ( Bipartite + Union Find )

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 …

UVA 1267 Network ( DFS )

把需要被覆蓋的節點押進該深度的節點表裡,之後依次選擇深度最深的為覆蓋的節點,用貪婪的思維找尋其 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 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>…

UVA 10972 RevolC FaeLoN ( 偽SCC的橋BCC )

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

UVA 1357 Cells ( 水題時間戳記 )

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

UVA 11396 Claw Decomposition ( 水題二分圖判定 )

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 11354 Bond ( 最小瓶頸路徑 Kruskal + LCA )

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

UVA 1494 Qin Shi Huang's National Road System ( 次小生成樹 )

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