题目
P2916 [USACO08NOV]安慰奶牛Cheering up the Cow
分析
这题开始不是很懂它的意思，看了题解才懂的。举个例子：有一条边 a->b 那么假定我们从a点出发再回到a点，先从a点出发，加上a点权值和边权，再从b回到a 加上b点权值和边权，那么对于每一条边，他的边权是不是就等于边权 * 2 + 起点的边权 + 终点的边权呢？即 edge[i].w = t[edge[i].u] + t[edge[i].v] + edge[i].w * 2
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std
;
int f
[10005], t
[10005];
struct Edge
{
int u
;
int v
;
int w
;
}edge
[100005];
int cmp(Edge a
, Edge b
)
{
return a
.w
< b
.w
;
}
int getf(int x
)
{
if (f
[x
] == x
)
{
return x
;
}
int fx
= getf(f
[x
]);
return f
[x
] = fx
;
}
int merge(int u
, int v
)
{
int t1
= getf(f
[u
]);
int t2
= getf(f
[v
]);
if (t1
!= t2
)
{
f
[t1
] = t2
;
return 1;
}
return 0;
}
int main()
{
int n
, m
, ans
= 0x3f3f3f3f;
scanf("%d%d", &n
, &m
);
for (int i
= 1; i
<= n
; i
++)
{
f
[i
] = i
;
scanf("%d", &t
[i
]);
ans
= min(ans
, t
[i
]);
}
for (int i
= 1; i
<= m
; i
++)
{
int u
, v
, w
;
scanf("%d%d%d", &u
, &v
, &w
);
edge
[i
] = {u
, v
, w
};
edge
[i
].w
= t
[edge
[i
].u
] + t
[edge
[i
].v
] + edge
[i
].w
* 2;
}
sort(edge
+ 1, edge
+ 1 + m
, cmp
);
int cnt
= 0;
for (int i
= 1; i
<= m
; i
++)
{
if (merge(edge
[i
].u
, edge
[i
].v
))
{
ans
+= edge
[i
].w
;
cnt
++;
}
if (cnt
== n
- 1)
{
break;
}
}
printf("%d\n", ans
);
return 0;
}
