43059 0906 - Power Grid poao899 Accepted C++ 0.600 2011-03-23 14:12:06 .
.
要仔細看清楚題目啊orz...
1. 每個邊都要走過至少一遍
2. 不能繞路
3. 城市只會出現在葉子
4. 點心數目範圍
考量某個節點：
每個子樹邊權和依序為A1 A2 A3 A4...An
每個子樹有點心的點數依序為B1 B2 B3 B4...Bn
那假設他走訪順序是s1 s2 s3 s4 ... sn
那麼浪費掉的點心是2 * [ As1 * ( Bs2+...+Bsn ) + As2 * ( Bs3+...+Bsn ) + ... + As(n-1) * ( 0 ) ]
先不要看這個式子，我們先把題目特殊化，假設所有的B都=1
那麼很逗趣的，浪費點心的式子變成：
2 * [ As1 * (n-1) + As2 * (n-2) + ... + As(n-1) * (0) ]
很明顯可以用排序不等式證明，A越小的要越先走。那麼我們回到一般化的問題：
如何使之極小化呢？想像把一個邊權和Ak 點數Bk的子樹拆成Bk個子樹 每個的A=(Ak/Bk)、這樣每個新子樹的B都會是1了
那麼利用上述結論會發現，Ak/Bk越小的子樹應該先走。顯然是一個正確的貪心策略
值得一提的是假設沒有上述性質2. 就可能出現先走一棵走一半之類的，就不知道怎做了orz
