最小生成树水题,先按最小生成树做,答案最后加上最小的从第i号楼接线到外界供电设施所需要的费用即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn = ;
struct abc{int uu, vv, cc;}node[maxn*(maxn - ) / + ];
int uu[maxn*(maxn - ) / + ];
int vv[maxn*(maxn - ) / + ];
int cc[maxn*(maxn - ) / + ];
int ff[maxn], father[maxn];
bool cmp(const abc&a, const abc&b) { return a.cc < b.cc; } int find(int x)
{
if (x != father[x]) father[x] = find(father[x]);
return father[x];
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int i, n, m;
scanf("%d%d", &n, &m);
for (i = ; i < m; i++) scanf("%d%d%d", &uu[i], &vv[i], &cc[i]);
for (i = ; i < n; i++) scanf("%d", &ff[i]);
for (i = ; i <= n; i++) father[i] = i;
for (i = ; i < m; i++)
{
node[i].uu = uu[i];
node[i].vv = vv[i];
node[i].cc = cc[i];
}
sort(node, node + m, cmp);
sort(ff, ff + n);
int anss = ;
for (i = ; i < m; i++)
{
int fu = find(node[i].uu);
int fv = find(node[i].vv);
if (fu != fv)
{
father[fu] = fv;
anss = anss + node[i].cc;
}
}
printf("%d\n", anss + ff[]);
}
return ;
}