描述 Description
Farmer John 变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接 N (5 <= N <= 10,000)个牧场, 牧场被连续地编号为 1..N. 每一个牧场都是一个奶牛的家. FJ 计划除去 P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间的连通性. 你首先要决定那些道路是需要保留的 N-1 条道路. 第 j 条双向道路连接了牧场 S_j 和 E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j), 而且走完它需要 L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接. 奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次你到达第 i 个牧场的时候 (即使你已经到过), 你必须花去 C_i (1 <= C_i <= 1,000) 的时间和奶牛交谈. 你每个晚上都会在同一个牧场 (这是供你选择的) 过夜, 直到奶牛们都从悲伤中缓过神来. 在早上起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的交谈任务. 假设 Farmer John 采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间. 对于你前 10 次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.
输入格式 InputFormat
第 1 行: 用空格隔开的两个整数 N 和 P.
第 2..N+1 行: 第 i+1 行包含了一个整数: C_i.
第 N+2..N+P+1 行: 第 N+j+1 行包含用空格隔开的三个整数: S_j, E_j 和 L_j.
输出格式 OutputFormat
第 1 行: 一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间).
样例输入 SampleInput
10 25
22
4
96
26
33
79
2
2
80
43
2 6 39
1 8 62
1 7 1
2 3 46
1 4 6
3 6 14
9 8 90
6 1 88
7 2 19
2 5 29
4 7 99
4 3 48
5 9 74
3 7 98
4 6 88
1 5 29
10 9 12
2 1 83
8 10 8
7 5 85
8 5 50
6 9 44
8 3 64
6 8 86
5 6 2
样例输出 SampleOutput
878
来源 Source
Gold
代码 Code
最小生成树。边权为两倍路上所需的时间加上两个端点牧场所需的时间。因为要回到一个点过夜，所以答案加上最小的点权。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/11.27;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
struct edge
{
int u,v,w;
bool operator < (const edge &temp) const
{
return w<temp.w;
}
}e[100005];
int fa[10005],c[10005];
int p,minc,ans;
int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
int main()
{
read(n);read(p);
minc=inf;
for (i=1;i<=n;i++) read(c[i]),minc=min(minc,c[i]);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=p;i++)
{
read(x);read(y);read(z);
e[i].u=x;e[i].v=y;
e[i].w=c[x]+c[y]+2*z;
}
sort(e+1,e+p+1);
ans=minc;
for (i=1;i<=p;i++) if (getfa(e[i].u)!=getfa(e[i].v))
{
fa[getfa(e[i].u)]=e[i].v;
ans+=e[i].w;
}
printf("%d\n",ans);
return 0;
}