洛谷 CF437C The Child and Toy（贪心）

传送门

---

解题思路

贪心策略：对于每一条边，先删除两个端点中权值大的那个点。

证明（感性）：

首先，删点其实就等于删边。对于每一条边，假设它的两个端点为a,b且a的权值>b的权值，那么先删a点对答案的贡献为b，先删b点对答案的贡献为a，因为求的是最小值，所以先删权值大的点。

AC代码

#include<iostream>
using namespace std;
int n,m,a[5005];
long long ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        ans+=a[u]<a[v]?a[u]:a[v];
        
    }
    cout<<ans;
    return 0;
}