Farmer John變得非常懶，他不想再繼續維護供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續地編號為1到N。每一個牧場都是一個奶牛的家。FJ計劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因為她們的交通系統被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達第i個牧場的時候(即使你已經到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務。假設Farmer John采納了你的建議，請計算出使所有奶牛都被安慰的最少時間。

第1行包含兩個整數N和P。

接下來N行，每行包含一個整數Ci。

接下來P行，每行包含三個整數Sj, Ej和Lj。

5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。

題意大致是，N個點留下N-1條路，從某個點出發走遍所有點，每條路耗時L，每到一個點耗時C，最后回到出發點。

注意出發點有兩次耗時，出發前一次，回來后一次。

邊權等于每條路走兩次耗時，到邊起點的耗時，與到邊終點的耗時的和，答案等于最小生成樹加上出發前的一次耗時（選最小點權）。

最小生成樹（連接所有點的邊權和最小的樹） 

Kruskal算法

準備階段

初始化所有點為樹，為邊權排序

實施階段

邊按邊權從小到大枚舉，如果兩個點屬于兩棵樹，按照這條邊連接這兩棵樹。

直到最小生成樹形成。

具體細節

并查集實現樹

并查集（不相交集合）

一維數組實現并查集 每個下標代表一個元素，數組值代表他的父節點，根節點的數組值等于下標，由此形成一棵樹。

查找：路徑壓縮，每次查找都一個點一個點找，耗時長，因為不考慮具體連接方式，遍歷過的點直接接到根節點上

合并：一個集合的根節點連到另一個集合的根節點上

列表用來按照邊權排序邊的序號，避免結構體交換耗時長

#include <cstring>#include <cstdio>#include <iostream>#include<algorithm>using namespace std;#define max(a,b) ((a>b)?(a):(b))int C[10100]={0},S[100010]={0},E[100010]={0},L[100010]={0},W[100010]={0};int BCJ[10010]={0},ord[100010]={0};int N,P,sum=0;bool cmp(int i,int j){return W[i]<W[j];}void build(){int i;for(i=1;i<=N;i++){    BCJ[i]=i;}for(i=1;i<=P;i++){    W[i]=2*L[i]+C[E[i]]+C[S[i]];    ord[i]=i;}sort(ord+1,ord+P+1,cmp);}int exam(int node){return BCJ[node]==node?node:BCJ[node]=exam(BCJ[node]);}int main(){int i;scanf("%d%d",&N,&P);for(i=1;i<=N;i++){    scanf("%d",&C[i]);}for(i=1;i<=P;i++){    scanf("%d%d%d",&S[i],&E[i],&L[i]);}build();int k=0,u,v,j;for(i=1;i<=P;i++){    j=ord[i];    if((u=exam(E[j]))!=(v=exam(S[j]))){        sum+=W[j];        BCJ[u]=v;        k++;        //PRintf("%d",W[j]);    }    if(k==N-1)break;}sort(C+1,C+N);printf("%d",sum+C[1]);return 0;}