原題：
https://jzoj.net/senior/#contest/show/2043/1
題目描述：
你在玩電子游戲的時候遇到了麻煩赞赖。甜害。。卑硫。徒恋。。 你玩的游戲是在一個虛擬的城市里進行欢伏，這個城市里有n個點入挣，都從0~n-1編了號，每兩個點之間有且僅有一條路徑∠跖。現(xiàn)在径筏，你的敵人到這個城市來踩點了!!!為了阻止他們更好的踩點葛假， 你決定切斷他們所有踩點人員的聯(lián)系，使他們孤軍作戰(zhàn)滋恬，然后在各個擊破聊训。但是這就要切斷某些街道，而你每切斷一條路恢氯，市民就會產(chǎn)生相對的不滿值带斑，不滿值越大，城市的和諧度就越小勋拟。所以你現(xiàn)在需要知道為了使踩點人員所在的點兩兩之間不聯(lián)通所切斷的邊產(chǎn)生的最小不滿值是多少勋磕？
輸入：
第一行一個數(shù)：n n<=50 以下n-1行，每行3個數(shù) a敢靡，b挂滓，c 表示a點和b點之間有條路，切斷這條路的不滿值為c 以下若干行 每行一個數(shù)啸胧，表示踩點人員的位置
輸出：
一個數(shù)赶站，最小不滿值
樣例輸入：
5 1 0 1 1 2 2 0 3 3 4 0 4 3 2 4
樣例輸出：
4
分析：
貪心+并查集
將所有邊從大到小依次加入圖中，加入后如無敵人則保留
若有敵人聯(lián)通吓揪，則刪除亲怠，統(tǒng)計答案
盡可能的保留較大邊
實現(xiàn)：
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for (int i=a;i<=b;i++)
#define N 55
using namespace std;
struct note
{
int x,y,z;
}a[51];
int dad[51],ans=0,q,n,xx,yy;
bool mk[51];
int get(int x){x==dad[x]?x:dad[x]=get(dad[x]);}
bool cmp(note a,note b){return a.z>b.z;}
int main()
{
scanf("%d",&n);
fo(i,1,n-1) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z),ans+=a[i].z;
while (scanf("%d",&q)!=EOF) mk[q]=true;
fo(i,1,n) dad[i]=i;
sort(a+1,a+1+n,cmp);
fo(i,1,n)
{
xx=get(a[i].x),yy=get(a[i].y);
if (xx==yy) ans-=a[i].z;
else if (!(mk[xx]&&mk[yy]))
{
dad[xx]=yy;
ans-=a[i].z;
if (mk[xx]) mk[yy]=true;
}
}
printf("%d\n",ans);
}
