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

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

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

接下來P行，每行包含三個整數S_j, E_j和L_j。

5 <= N <= 10000，N-1 <= P <= 100000，0 <= L_j <= 1000，1 <= C_i <= 1,000。

思路：

這道題著實把我惡心到了，題目題意表述不清，測試樣例錯誤。

先把正確的輸入樣例給出來：

5 71010206301 2 52 3 52 4 123 4 172 5 153 5 64 5 12

輸出還是 176

題目題意表述不清，剛開始以為是每天只去拜訪一家農場，只安慰一頭奶牛。然后忽略了一局關鍵的話：你每個晚上都會在同一個牧場(這是供你選擇的)過夜

剛開始的思路是這樣的，先按照邊權求出一顆最小生成樹，然后訪問的時候在考慮每個農場安慰的時間

如上圖，假設按照邊權獲得了一顆最小生成樹，然后從頂點1出發，按照1~10的順序去訪問，那么每個頂點的訪問此書就是自身度數的2倍，遍歷一次生成樹。但是頂點1要少多1次

早上從1出發，到2，然后在2這里過夜，第二天再從2出發到3...

然后事實成功證明這是錯的+_+

關鍵的話：你每個晚上都會在同一個牧場(這是供你選擇的)過夜

按照上圖的話，我每晚可能會在不同的農場過夜，如果要在同一個農場過夜，說明每天只能走一個分支然后回來

如上圖，1->2->3->2->1在1這里過夜  1->4->1 在1這里過夜  1->5->6->5->1最后回到1

這樣的話就能保證每晚在一個農場過夜

但是這樣算出來的結果還是錯誤的，因為邊權的數值改變了。如果單純的之按照輸出進來的數值作為邊權，的確是一個最小生成樹，但是總時間里面還會受到點權的影響，這樣得出來的時間并不能夠保證是最小值。

所以，邊權的數值需要變動。和上面的規律一樣，每個點的訪問次數是自身點度數的2倍，始點多一次。所以我們可以把點權加入到邊權中。一條邊的邊權等于邊權+兩端頂點的點權。正好遍歷一次每條訪問兩次。再加上剛開始始點多出來的一次就可以了。

另外，在吐槽一下，為什么我用不壓縮路徑的并查集得出來的結果差那么多，貌似以前也遇到過這種問題，老老實實用帶路徑壓縮的吧。

AC代碼：

#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN=100005;struct node{    int s;//始點    int e;//終點    int comfort_time;//邊權}edge[MAXN];//定義邊集數組int v[MAXN];//點權int father[MAXN];bool cmp1(node a, node b)//頂點權重比較函數{    return a.comfort_time<b.comfort_time;}int Find(int x){    if(father[x]!=x)    {        int temp=Find(father[x]);        father[x]=temp;        return temp;    }    return x;}int krusal(int N, int P){    sort(edge+1,edge+P+1,cmp1);    int cost=0;    for(int i=0;i<=N;i++)    {        father[i]=i;    }    int cnt=0;    for(int i=1;i<=P;i++)    {        int fe=Find(edge[i].e);        int fs=Find(edge[i].s);        if(fs!=fe)        {            father[fs]=fe;            cost+=edge[i].comfort_time;            cnt++;        }        if(cnt==N-1)            break;    }    return cost;}int main(){    int N,P;    int cnt_time=0;    scanf("%d %d",&N,&P);    for(int i=1;i<=N;i++)        scanf("%d",&v[i]);    for(int i=1;i<=P;i++)    {        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);        edge[i].comfort_time=2*edge[i].comfort_time+v[edge[i].e]+v[edge[i].s];    }    cnt_time+=krusal(N,P);    sort(v+1,v+N+1);    cnt_time+=v[1];    PRintf("%d/n",cnt_time);    return 0;}第一種想法的代碼（警戒自己）：
#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN=100005;struct node{    int s;//始點    int e;//終點    int comfort_time;//邊權}edge[MAXN];//定義邊集數組struct vertex{    int weight;//點權    int postion;//輸入進來時候的位置}v[MAXN];//定義每個點自身花費的時間int father[MAXN];int flag[MAXN];//標記數組int du[MAXN];//頂點的度數bool cmp1(node a, node b)//頂點權重比較函數{    return a.comfort_time<b.comfort_time;}bool cmp2(vertex a, vertex b)//邊權比較函數{    return a.weight<b.weight;}bool check(int N)//檢查是否所有的點都已經遍歷完成{    for(int i=1;i<=N;i++)        if(!flag[i])            return false;    return true;}int Find(int x){    if(father[x]!=x)        father[x]=Find(father[x]);    return father[x];}void unionn(int x, int y){    int fa=Find(x);    int fb=Find(y);    if(fa!=fb)        father[x]=y;}int krusal(int N, int P){    sort(edge+1,edge+P+1,cmp1);    int cost=0;    memset(flag,false,sizeof(flag));    memset(du,0,sizeof(du));    for(int i=0;i<=N;i++)    {        father[i]=i;    }    int index=1;//選擇邊的下標    while(!check(N))    {        if(Find(edge[index].e)!=Find(edge[index].s))        {            unionn(edge[index].e,edge[index].s);            cost+=edge[index].comfort_time;            flag[edge[index].e]=true;            flag[edge[index].s]=true;            du[edge[index].e]++;            du[edge[index].s]++;        }        index++;    }    return cost;}int main(){    int N,P;    int cnt_time=0;    scanf("%d %d",&N,&P);    for(int i=1;i<=N;i++)    {        scanf("%d",&v[i].weight);        v[i].postion=i;    }    for(int i=1;i<=P;i++)    {        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);    }    cnt_time+=2*krusal(N,P);    sort(v+1,v+N+1,cmp2);    cnt_time+=(du[v[1].postion]+1)*v[1].weight;    for(int i=2;i<=N;i++)    {        cnt_time+=du[v[i].postion]*v[i].weight;    }    printf("%d/n",cnt_time);    return 0;}