Problem Description: You are given a directed weighted graph with N nodes and M edges. Q queries follow: OP = 1: Output the shortest path from node 1 to node V. OP = 2: Read C values, the C[i]'th edge should have its weight incremented by …

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

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…

UVa Online Judge 可以先依據邊的溫度求最小瓶頸生成樹，但這裡生成的條件是起點和終點為同一個連通分量即可。求出最小溫度後對這些邊求起點至終點的最短路徑就行了。無聊寫了SPFA跟Dijkstra，運行時間一模一樣。 #include <bits/stdc++.h> using namespace std; const int </bits/stdc++.h>…

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

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