首页 > 代码库 > Codeforces Round #250 (Div. 2) C、The Child and Toy
Codeforces Round #250 (Div. 2) C、The Child and Toy
注意此题,每一个部分都有一个能量值v[i],他移除第i部分所需的能量是v[f[1]]+v[f[2]]+...+v[f[k]],其中f[1],f[2],...,f[k]是与i直接相连(且还未被移除)的部分的编号。
注意题目移除的都是与第i部分直接相连的部分的能量值,
将本题目简化得,只考虑两个点1和2,1和2相连,1的能量值是10,2的能量值是20,
移除绳子时,要保持能量最小,可以移除部分2,这样移除的能量就是与2相连的部分1的能量即是10;
故每次相连两部分都移除能量值大的即可
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int n,m,ans = 0; cin >> n >> m; vector<int> v(n+1); for(int i = 1 ;i <= n ; ++ i) cin >> v[i]; for(int i = 0 ; i < m; ++ i){ int x,y; cin >> x >> y; ans +=min(v[x],v[y]); } cout<<ans<<endl; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。