正題

---

題目大意

一棵樹n個點
有k個點被占領，刪除每一條邊都有不同的代價，然后要求所以被占領的點相互隔開，代價最小。

---

解題思路

我們可以考慮反構(gòu)圖，將邊權(quán)排序，然后對于每條邊，如果加入這條邊后不會使敵軍連接就加這條邊，然后加入，然后用并查集判斷敵軍是否連接。

---

code

#include<cstdio> #include<algorithm> #define N 100010 using namespace std; struct node{int x,y,w; }a[N]; int n,k,tot,father[N]; long long ans; bool army[N]; int find(int x)//找祖先 {return father[x]==x?x:father[x]=find(father[x]); } bool cmp(node x,node y) {return x.w>y.w;} int main() {scanf("%d%d",&n,&k);for(int i=1;i<=k;i++){scanf("%d",&tot);tot++;army[tot]=true;}for(int i=1;i<n;i++){father[i]=i;scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);a[i].x++;a[i].y++;ans+=a[i].w;}father[n]=n;sort(a+1,a+n,cmp);for(int i=1;i<n;i++){int fa=find(a[i].x),fb=find(a[i].y);if(army[fa]&&army[fb]) continue;//會使軍隊連接ans-=a[i].w;father[fa]=father[fb];//連接army[fa]=army[fb]=army[fa]|army[fb];//計算軍隊}printf("%lld",ans); }

總結(jié)

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

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