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

第1行包含兩個(gè)整數(shù)N和P。

接下來N行，每行包含一個(gè)整數(shù)C_i。

接下來P行，每行包含三個(gè)整數(shù)S_j, E_j和L_j。

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

思路：

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

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

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

輸出還是 176

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

剛開始的思路是這樣的，先按照邊權(quán)求出一顆最小生成樹，然后訪問的時(shí)候在考慮每個(gè)農(nóng)場安慰的時(shí)間

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

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

然后事實(shí)成功證明這是錯(cuò)的+_+

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

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

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

這樣的話就能保證每晚在一個(gè)農(nóng)場過夜

但是這樣算出來的結(jié)果還是錯(cuò)誤的，因?yàn)檫厵?quán)的數(shù)值改變了。如果單純的之按照輸出進(jìn)來的數(shù)值作為邊權(quán)，的確是一個(gè)最小生成樹，但是總時(shí)間里面還會受到點(diǎn)權(quán)的影響，這樣得出來的時(shí)間并不能夠保證是最小值。

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

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

AC代碼：

#include<iostream>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>using namespace std;const int MAXN=100005;struct node{    int s;//始點(diǎn)    int e;//終點(diǎn)    int comfort_time;//邊權(quán)}edge[MAXN];//定義邊集數(shù)組int v[MAXN];//點(diǎn)權(quán)int father[MAXN];bool cmp1(node a, node b)//頂點(diǎn)權(quán)重比較函數(shù){    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;//始點(diǎn)    int e;//終點(diǎn)    int comfort_time;//邊權(quán)}edge[MAXN];//定義邊集數(shù)組struct vertex{    int weight;//點(diǎn)權(quán)    int postion;//輸入進(jìn)來時(shí)候的位置}v[MAXN];//定義每個(gè)點(diǎn)自身花費(fèi)的時(shí)間int father[MAXN];int flag[MAXN];//標(biāo)記數(shù)組int du[MAXN];//頂點(diǎn)的度數(shù)bool cmp1(node a, node b)//頂點(diǎn)權(quán)重比較函數(shù){    return a.comfort_time<b.comfort_time;}bool cmp2(vertex a, vertex b)//邊權(quán)比較函數(shù){    return a.weight<b.weight;}bool check(int N)//檢查是否所有的點(diǎn)都已經(jīng)遍歷完成{    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;//選擇邊的下標(biāo)    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;}