点击打开链接
题意:有n点,m条边 每个点有价值a[i] 删除一点所需代价为当前和它相连的a[j]之和,求删除n个点的最小代价 n,m<=2e3
删除一个点也就删除了它所有的边,若从边的角度来考虑: 一条边(u,v)被删除的代价为a[u]或者a[v],(若a[u]>a[v]),所以从a[u]大的点开始删除,使得每条边被删除的代价都最小
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; const int N=2e5+20; ll n,m,vis[N],a[N]; vector<int> e[N]; void solve() { memset(vis,0,sizeof(vis)); ll ans=0; //O(n^2) for(int i=1;i<=n;i++) { ll mx=0,u=1; //找到a值最大的u for(int k=1;k<=n;k++) { if(vis[k]==0&&a[k]>=mx) { mx=a[k]; u=k; } } vis[u]=1; for(int k=0;k<e[u].size();k++) { int v=e[u][k]; if(vis[v]==0) ans+=a[v]; } } cout<<ans<<endl; } int main() { while(cin>>n>>m) { for(int i=1;i<=n;i++) e[i].clear(); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) { int u,v; cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } solve(); } return 0; }