一開始以為題很難，當我坐下來認真讀題后，卻神奇地發(fā)現(xiàn)這道題很水……

　　這和Kruskal有什么區(qū)別啊？

　　于是我開開心心地十五分種敲完了代碼~

　　然后我就Wa了……

　　emmm……

　　尷尬……

　　一開始我對于每一個點的no[]值都進行維護，時間復(fù)雜度特別高，于是就Wa了qwq

　　后來我發(fā)現(xiàn)，其實一顆樹只要維護一個no，即根結(jié)點的no即可，這樣判斷這棵樹數(shù)是否包含那k個城市的時候。只要看根節(jié)點就可以了。

　　那么對于樹的相連，看哪一棵樹的根節(jié)點有no，就繼續(xù)作為根節(jié)點；如果都沒有，直接加邊就可以，如果都有，這條邊就不能連啦~

　　簡單地總結(jié)一下，先貪心排序，再正常連邊，判斷是否能連，一訪問到no就直接將其作為根結(jié)點，便于以后的訪問。

　　還有，開long long（別問我是怎么知道的）……

　　其實寫代碼的時候注意到有關(guān)no轉(zhuǎn)移的技巧，這就是一道提高減的題，根本沒什么難度。

　　上代碼：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define maxn 100005 #define int long long struct data {int x,y,w; } q[maxn]; int n,k,sum,par[maxn]; bool no[maxn],flag; bool cmp(data a,data b) {return a.w>b.w; } int find(int x) {if(x==par[x])return x;return par[x]=find(par[x]); } main() {scanf("%lld%lld",&n,&k);for(int i=0; i<n; i++)par[i]=i;for(int i=0; i<k; i++){int a;scanf("%lld",&a);no[a]=1;}for(int i=0; i<n-1; i++){int a,b,c;scanf("%lld%lld%lld",&a,&b,&c);q[i].x=a;q[i].y=b;q[i].w=c;}sort(q,q+n-1,cmp);for(int i=0; i<n-1; i++){if(no[find(q[i].x)]&&no[find(q[i].y)]){sum+=q[i].w;continue;}int nx=find(q[i].x);int ny=find(q[i].y);if(no[ny])par[nx]=ny;elsepar[ny]=nx;}printf("%lld",sum);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/popo-black-cat/p/10054270.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的P2700 逐个击破的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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