网站关键词如何做,做外贸是在什么网站,长垣网站建设,郴州旅游攻略正题
题目链接:https://ac.nowcoder.com/acm/contest/1111/J 题目大意
一棵树#xff0c;每个点有一个威力值#xff0c;每次破坏一个点会受到与它相连没有破坏的点的威力值之和的伤害。求破坏所有点的最小伤害。 解题思路
因为是一棵树#xff0c;所有我们可以看为每条边…正题
题目链接:https://ac.nowcoder.com/acm/contest/1111/J 题目大意
一棵树每个点有一个威力值每次破坏一个点会受到与它相连没有破坏的点的威力值之和的伤害。求破坏所有点的最小伤害。 解题思路
因为是一棵树所有我们可以看为每条边两边的点选择一个先破坏显然先破坏威力值高的点因为没有环所有这些边之间的选择不会相互影响所以先从威力值大的破坏到小的即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e5100;
struct node{int to,next;
}a[N*2];
int n,p[N],num[N],ls[N],ans,tot;
bool v[N];
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
bool cmp(int x,int y)
{return p[x]p[y];}
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,p[i]),num[i]i;for(int i1;in;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);}sort(num1,num1n,cmp);for(int i1;in;i){int xnum[i];for(int jls[x];j;ja[j].next)if(!v[a[j].to]) ansp[a[j].to];v[x]1;}printf(%d,ans);
}
