洛谷 CF437C The Child and Toy(贪心)

传送门


 

解题思路

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

证明(感性):

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

AC代码

 1 #include<iostream>
 2 using namespace std;
 3 int n,m,a[5005];
 4 long long ans;
 5 int main(){
 6     cin>>n>>m;
 7     for(int i=1;i<=n;i++) cin>>a[i];
 8     for(int i=1;i<=m;i++){
 9         int u,v;
10         cin>>u>>v;
11         ans+=a[u]<a[v]?a[u]:a[v];
12         
13     }
14     cout<<ans;
15     return 0;
16 }
上一篇:Gitstats的安装及使用


下一篇:洛谷 CF1153B Serval and Toy Bricks