【CF437C】The Child and Toy

时间:2022-04-22 21:50:32

题目大意:给定一个有 N 个点,M 条边的无向图,点有点权,删除一个点就要付出所有与之有联系且没有被删除的点的点权之和的代价,求将所有点删除的最小代价是多少。

题解:从图连通性的角度出发,删除所有点就意味着需要删除所有的边。现在来考虑每条边对答案的贡献,由于所有边均需要被删除,才能使得原图完全不连通,因此只需要在删除该边的同时,将连接该边端点的两个点中点权较小的值加入答案贡献即可,即:意味着优先删除点权大的点。

代码如下

#include <bits/stdc++.h>
using namespace std; int n,m,w[1010];
long long ans; void read_and_parse(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
} void solve(){
while(m--){
int x,y;
scanf("%d%d",&x,&y);
ans+=min(w[x],w[y]);
}
printf("%lld\n",ans);
} int main(){
read_and_parse();
solve();
return 0;
}