前幾天上立志的GRAPH課大開眼界...知道GRAPH世界好大好大, 目前第一步還是先把TEXTBOOK PROBLEM學好, CODE得出 CODE得快。
做了幾道GRAPH題, 再把matching , AP, bridge那些相關題目做多一點就要轉攻geom了吧..?
雖說regional 出的機率很小就是了..
Codeforces #88C
很特殊既一題graph...雖然佢地大家都覺得好頹..
比賽中我fail system test, 但原來係錯柒bug...一有得practice再改就過了..起碼諗法係岩既
given 1個tournament (ref: http://en.wikipedia.org/wiki/Tournament_(graph_theory) )
verify 有無 3-length cycle, 有則output 任意一個solution( 3 個vertex id), 無則output -1
畫呀畫, 畫呀畫, 發現由於圖特殊
如果搵到any length既directed cycle, 呢個cycle入面一定就有 3-length cycle
我估大約可以用mi proof, but 可以畫幅類似self explained既圖:
好, 當claim已岩, 點搵 呢個3-length cycle出黎呢?
by observation(雖然場上係帶點guessing), 呢個3-length cycle 其中 2粒一定係連住(可以試下掉轉d 紅線試下)
So...Algo 就係:
1. DFS 搵DIRECTED CYCLE
2. N^2 睇下有無 a_i, a_i+1, ???? 造成3-length cycle
ps: step 2 chin爺貌似係O(n) 都做到, GG/ whh 直頭唔係咁做...sign
ICPC4218
Training 既一題題目...其實過左都好似無過咁, 覺得下次未必做得出..at least比賽上做唔到的吧。
題目:
Given n個城市, 每個城市有兩支有顏色的旗, 假設城市A , 有R 旗及 B 旗
要進入A, 身上就要先帶住R旗或B旗;
當你離開某個城市時, 可以獲得另一種旗, i.e: 你用R旗進入A, 離開時則帶著B旗, or vice versa。
問: 任意從一個城市開始, 能否travel 全部城市, 並且全部城市只經過一次? 如果可以則output 開始的城市id , multiple ans時則output id最小的。
當時完全無idea。之後學會euler path, 知道此題係euler path應用題。
跟uva necklace 一樣, 將顏色當做node, 城市當做edge, 有self loop 和 multiple edges, 問題便由NPC的TSP 變成P 的euler path了。
然後還剩一個問題: 如何找id 最小的起始點? 來個分析:
1. 先查existence of euler path: connected 和 odd degree node = 0 or 2
2. 若odd degree node = 0, 就是有euler circuit了, 就是從任何點出發都可以, 所以 答案直接就是最小的城市id
3. 若odd degree node = 2, 可以出發的城市(亦即圖中的edge) 就是這兩個node 連住的 edge
問題是要找出可以行並且id 最細的城市( 就是說是圖中的edge啦, edge!)
idea 就是: remove 該條edge, 然後check 圖會否變成edge disjoint。
==> simply dfs
然而 implement上好多野要注意...亦係我擔心既主因, implement 上可以
查哂所有edge, 當 兩端有一粒係 odd degree先進一步test。
PS: 呢題最煩係個INPUT...亂咁黎, 轉換成graph 都搞左好一陣...
ICPC4210
係acm wiki上面搵到既practice 題目, Singapore 2007年。
被chin爺X, 因為話咁樣又少左一個SITE 用黎打team training...我都係睇左呢題姐..
題意:
given 一個connected SIMPLE undirected weighted graph, 圖中可能會有好多loop, 問如果每個loop 上面都最小要pick一條edge, minimum total cost係幾多
kn一句: 試下exhaust 所有你識既graph algo。
果然很快就發現, 根本就係maximum spanning tree嘛
原圖減走max spanning tree就係要安裝偷拍器材既road
今日再認真諗下correctness先code, 覺得好直觀嘛?
因為spanning tree T, for 每一個loop 當有n 條edge, 咁T 一定係包左入面n-1 條weight最大的edge,
剩番個條就係cover左呢個loop 而 cost最小既edge了 。
夾硬要話有咩theorem, 我會覺得係326學既red rule定blue rule吧?
POJ3522
kn比既一條題目, interesting~
題意:
define SLIMNESS(瘦度?) of a spanning tree T is the highest T's edge cost - smallest T's edge cost
given 一個simple graph, 係眾多spanning tree 入面, find the one with smallest slimness。(just output the required slimness)
無咩idea as well, 諗左一陣, 發現題目好好, given 埋spanning tree既definition; 而入面又強調: spanning tree係 for n vertex, 有n-1 條edge...
加上圖係simple,
我就發現...有個頹algo!! 其實就係greedy 咁試..
先sort by weight,
試諗下, 當 edge i 係某spanning tree入面weight 最細既edge
咁我要搵多 n-2條edge such that 佢地form到一棵tree。
假設所有 edge j, for all j > i, 都係possible既edge, 咁第 (i + (n-2)) 條edge 一定係最optimal
(因為第 (i+(n-1)) 條edge 或者之後既edge, weight 都會再大d, 自然difference 就再大d了.. 對於同一個minimum edge i 黎講)
所以algo就好明顯了
1. sort m 條edge by it's weight
2 fix i as minimum weight edge, linearly find n-2 more possible edge (by disjoint set checking, like normal mst algorithm!) for all i !
3 take minimum !!
嗚呀..其實, 好似仲未點做過matching / bridge / AP 既題目, 仲有geom, 仲有simulation
其實仲有fyp * 2, 仲有414...嗚呀呀呀呀呀呀呀呀呀呀呀呀!!!!!!!!
