0w1

Graph

CFR 794 D. Labelling Cities ( Ad hoc, Graph )

Problem - 794D - Codeforces題意: 有 N 個城市,M 條路。如果存在,輸出一個方案,為每個城市 u 分配一個數字 X[ u ],使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約: N, M ≤ 3e5解法: 首先考慮這樣的一對城市 ( u, v ):它們的鄰接陣列,…

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