首页 > 代码库 > CF(437C)The Child and Toy(贪心)
CF(437C)The Child and Toy(贪心)
题意:给出一个无向图,每个点有点权,操作是一个一个将所有点揪走直至剩下一个点,揪走一个点的代价是剩下点中与其连边的点的点权和。求完成操作所需花费的最小代价。
解法:贪心的思想,每次将剩余点中点权最大的点揪出,这样可以保证每条边都是会选择相对小的点权被消耗掉。所以直接输出所有边的边权和即可。
代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=10100; const int INF=1000000007; int num[Max]; int n,m; int main() { cout<<390/21.0<<endl; while(scanf("%d%d",&n,&m)==2) { for(int i=1;i<=n;i++) scanf("%d",num+i); int ans=0; for(int i=0;i<m;i++) { int a,b;scanf("%d%d",&a,&b); ans+=min(num[a],num[b]); } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。