正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1111/J

---

題目大意

一棵樹(shù)，每個(gè)點(diǎn)有一個(gè)威力值，每次破壞一個(gè)點(diǎn)會(huì)受到與它相連沒(méi)有破壞的點(diǎn)的威力值之和的傷害。求破壞所有點(diǎn)的最小傷害。

---

解題思路

因?yàn)槭且豢脴?shù)，所有我們可以看為每條邊兩邊的點(diǎn)選擇一個(gè)先破壞，顯然先破壞威力值高的點(diǎn)，因?yàn)闆](méi)有環(huán)，所有這些邊之間的選擇不會(huì)相互影響，所以先從威力值大的破壞到小的即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+100; 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].to=y;a[tot].next=ls[x];ls[x]=tot; } bool cmp(int x,int y) {return p[x]>p[y];} int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&p[i]),num[i]=i;for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}sort(num+1,num+1+n,cmp);for(int i=1;i<=n;i++){int x=num[i];for(int j=ls[x];j;j=a[j].next)if(!v[a[j].to]) ans+=p[a[j].to];v[x]=1;}printf("%d",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的牛客国庆集训派对day6TJ-DefenseTower【贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。