Codeforces 437C The Child and Toy：貪心策略證明與 O(n+m) 實現

此過程等價於：對每條邊，由權值較大的端點「貢獻」較小權值。

算法流程

1. 讀入 n, m 及 v[1..n]。
2. 建立鄰接表 g[u]。
3. 建立節點索引陣列 id[1..n]，按 v[id[i]] 降序排序。
4. vis[u] = false 初始化。
5. 遍歷排序後的節點 u：
       vis[u] = true
       對每個鄰居 to：若 !vis[to] 則 ans += v[to]。
6. 輸出 ans。

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, m, val[N];
vector<int> g[N];
int idx[N];
bool vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
        idx[i] = i;
    }
    sort(idx + 1, idx + n + 1, [&](int a, int b) {
        return val[a] > val[b];
    });
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        int u = idx[i];
        vis[u] = true;
        for (int v : g[u]) {
            if (!vis[v]) ans += val[v];
        }
    }
    cout << ans << '\n';
    return 0;
}

複雜度分析

• 排序：O(n log n)
• 遍歷邊：每條邊在兩端點中較大者被處理時計算一次 → O(m)
• 總時間：O(n log n + m)，n ≤ 1000, m ≤ 2000 極輕鬆。
• 空間：O(n + m)。

為什麼這是貪心？

雖然總代價與順序無關，但「按權值從大到小處理」提供了一種 構造性證明：
當處理最大權值節點時，其所有邊的代價已確定為鄰居權值；隨後遞歸處理剩餘子圖。這將問題分解為最優子結構，符合貪心選擇性質。

延伸思考

• 若代價定義為 max(v[u], v[v])，答案同理為 ∑ max(...)。
• 若節點有刪除成本，邊代價為 min(節點刪除成本)，同樣套用。
• 本質上是 邊權 = 端點權函數 的圖論求和問題，無需 DP/流網絡。