LeetCode 3547. Maximum Sum of Edge Values in a Graph
weekly contest 449。
垃圾題，官方答案是錯的，不愧是垃扣。
好不容易打的 300 名大概要被 rejude。
題目
https://leetcode.com/problems/maximum-sum-of-edge-values-in-a-graph/description/
解法
隨便說說賽時的想法，代碼就不貼了，反正是錯的。
每個點至多兩個邊，所以圖的形狀只有兩種：
- 鍊狀
- 環狀
先 dfs 找出所有鍊和環的大小。
考慮如何填數字。
環可以貢獻的邊比較多，應該先填環、再填鍊。
環怎麼填？
為了讓較大的數靠在一起，最大的擺中間，然後由大至小左右交替填。
例：[..,7,9,10,8,6,..]
先填大環還是小環？
直覺是先填小環。但其實大小順序無關。
寫了個暴力腳本依隨機順序填若干個環，發現結果都一樣。
鍊怎麼填？
和環的貪心填法相同，差別在於要先填大的鍊。
較大鍊可以貢獻出更多的邊，更有機會讓大的數相乘；
孤立的單個節點也視作鍊，沒辦法貢獻分數，留到最後填較小的值。