P2916 [USACO08NOV] 安慰奶牛 Cheering up the Cow#
题目描述#
ジョンは N 個の牧場を持っており、番号は 1 から N までです。各牧場には 1 頭の牛が住んでいます。これらの牧場を結ぶ P 本の道路があり、各道路は双方向です。j 番目の道路は牧場 Sj と Ej を結び、通行には Lj の時間がかかります。2 つの牧場の間には最大 1 本の道路しかありません。ジョンは各牧場が接続された状態を保ちながら、できるだけ多くの道路を取り除くつもりです。
ジョンは、道路が強制的に取り壊された後、牛が非常に悲しむことを知っているので、道路を取り壊した後に彼女たちをなだめるつもりです。ジョンは任意の牧場から出発して、彼の安定化作業を開始することができます。彼がすべての牛を訪問した後、出発地点に戻る必要があります。牧場 i を通過するたびに、彼は牛と話すのに Ci の時間を費やさなければなりません。以前に作業を行った場合でも、再度話をする必要があります。ジョンは出発時と帰りの際に、出発地点の牛と話をする必要があります。ジョンがどの道路を取り壊すべきかを計算して、牛をなだめる時間を最小限に抑えることができるかを考えてください。
入力出力フォーマット#
入力フォーマット：
* Line 1: 2 つの空白で区切られた整数: N と P
* Lines 2..N+1: Line i+1 には単一の整数: C_i が含まれています
* Lines N+2..N+P+1: Line N+j+1 には 3 つの空白で区切られた整数: S_j, E_j, L_j が含まれています
出力フォーマット：
* Line 1: すべての牛を訪問するのにかかる総時間（寝ている牧場の牛への 2 回の訪問を含む）を示す単一の整数
入力出力サンプル#
入力サンプル #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------+
牧場4で目を覚まし、牧場の順番で4, 5, 4, 2, 3, 2, 1, 2, 4を訪問し、合計176の時間を得てから再び眠りに戻ります。
## 思路
私は、辺の重みを歩く時間と両端の会話時間の合計として設定し、ソートした後に最小生成木の選択結果を求める（サンプル）ことがサンプルの答えと一致することを発見しました。
したがって、どの辺を選択するかを求めた後、dfsを使用して総時間を求めるつもりです。
[hqx](https://cnblogs.com/perisino)大佬に知らせてください。大佬は厳密な推論を経て、辺の重みを2倍の通行時間と1倍の両端の時間に設定するだけで、最小生成木の和に最小の1つの点の会話時間を加えたものが最短の総時間になることを発見しました。
理由は、往復で各辺を2回通過するため（サンプルを観察/データを生成）、それぞれの消費は2つの端点の時間です。出発点は1回多く計算されます。
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;
}