P2916 [USACO08NOV] 安慰奶牛 Cheering up the Cow#
题目描述#
約翰有 N 個牧場，編號依次為 1 到 N。每個牧場裡住著一頭奶牛。連接這些牧場的有 P 條道路，每條道路都是雙向的。第 j 條道路連接的是牧場 Sj 和 Ej，通行需要 Lj 的時間。兩牧場之間最多只有一條道路。約翰打算在保持各牧場連通的情況下去掉儘量多的道路。
約翰知道，在道路被強拆後，奶牛會非常傷心，所以他計劃拆除道路之後就去忽悠她們。約翰可以選擇從任意一個牧場出發開始他維穩工作。當他走訪完所有的奶牛之後，還要回到他的出發地。每次路過牧場 i 的時候，他必須花 Ci 的時間和奶牛交談，即使之前已經做過工作了，也要留下來再談一次。注意約翰在出發和回去的時候，都要和出發地的奶牛談一次話。請你計算一下，約翰要拆除哪些道路，才能讓忽悠奶牛的時間變得最少？
输入输出格式#
輸入格式：
* Line 1: Two space-separated integers: N and P
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+P+1: Line N+j+1 contains three space-separated
integers: S_j, E_j, and L_j
輸出格式：
* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your
sleeping-pasture)
输入输出样例#
輸入樣例 #1：
5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12
輸出樣例 #1：
176
说明#
+-(15)-+
/ \
/ \
1-(5)-2-(5)-3-(6)--5
\ /(17) /
(12)\ / /(12)
4------+
Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2, 3, 2, 1, 2, 4 yielding a total time of 176 before going back to sleep.
## 思路
我發現把邊權設為走路的時間加上兩端談話的時間，排序之後求最小生成樹的選邊結果（樣例）跟樣例答案一樣。
所以打算按這樣求出選哪些邊之後dfs求總時間。
告訴[hqx](https://cnblogs.com/perisino)大佬，大佬經過嚴密的推論，發現只要把邊權設為兩倍路上時間加一倍的兩端時間，最小生成樹的和加上最少的一個點的談話時間，就是最短總時間。
理由是來回每條邊都會經過兩次（觀察樣例/造數據），分別消耗的是兩個端點的時間。出發點會多算一次。
HQX大佬TQL！
## CODE
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int MAXN=1000000+5,INF=0x3f3f3f3f;
int n,p;
int c[10005];
struct tu
{
struct edge
{
int p1,p2,w,a;
friend bool operator <(edge x,edge y)
{
return x.a<y.a;
}
} b[MAXN];
int newpe;
int head[MAXN];
int fa[MAXN];
bool v[MAXN];
void insert(int p1,int p2,int w)
{
b[++newpe].p1=p1;
b[newpe].p2=p2;
b[newpe].w=w;
b[newpe].a=2*b[newpe].w+c[p1]+c[p2];
}
int zxscs(void)//最小生成樹（原諒我不會打克魯斯卡爾）
{
sort(b+1,b+1+newpe);
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
int cnt=0;
int tot=0;
for(int i=1;i<=newpe;++i)
{
if(doFind(b[i].p1)!=doFind(b[i].p2))
{
++cnt;
tot+=b[i].a;
doUnion(b[i].p1,b[i].p2);
}
if(cnt==n-1)
{
return tot;
}
}
return 0;
}
void doUnion(int x,int y)
{
x=doFind(x);
y=doFind(y);
fa[x]=y;
}
int doFind(int x)
{
if(fa[x]==x)return x;
else return fa[x]=doFind(fa[x]);
}
} mp;
int main(void)
{
scanf("%d%d",&n,&p);
int minc=INF;
for(int i=1;i<=n;++i)
{
scanf("%d",c+i);
minc=min(c[i],minc);
}
for(int i=1;i<=p;++i)
{
int p1,p2,w;
scanf("%d%d%d",&p1,&p2,&w);
mp.insert(p1,p2,w);
}
int ans;
ans=mp.zxscs();
ans+=minc;
printf("%d\n",ans);
return 0;
}