NYOJ38, 布线问题

本文主要是介绍NYOJ38, 布线问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

南阳理工学院要进行用电线路改造，现在校长要求设计师设计出一种布线方式，该布线方式需要满足以下条件：
1、把所有的楼都供上电。
2、所用电线花费最少

输入

第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里，每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。（哪两栋楼间如果没有指明花费，则表示这两栋楼直接连通需要费用太大或者不可能连通）
随后的1行里，有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )
（楼的编号从1开始），由于安全问题，只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。

输出

每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。

样例输入

1
4 6
1 2 10
2 3 10
3 1 10
1 4 1
2 4 1
3 4 1
1 3 5 6

样例输出

4

来源

[张云聪]原创

 

 
//package NYOJ;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
while (t-- > 0) {
int v = cin.nextInt();
int e = cin.nextInt();
int[][] map = new int[v + 5][v + 5];
for (int i=0;i<map.length;i++)
Arrays.fill(map[i], Integer.MAX_VALUE);
for (int i = 1; i <= e; i++) {
int a = cin.nextInt();
int b = cin.nextInt();
int c = cin.nextInt();
map[a][b] = c;
map[b][a] = c;
}
for (int i = 1; i <= v; i++) {
int a = cin.nextInt();
map[0][i] = a;
map[i][0] = a;
}
int[] d = new int[v + 5];
boolean[] flag = new boolean[v + 5];
int ans = 0;
Arrays.fill(d, Integer.MAX_VALUE);
Arrays.fill(flag, false);
flag[1] = true;
for (int i = 1; i <= v; i++) {
d[i] = map[1][i];
}
for (int i = 1; i < v; i++) {
int min = Integer.MAX_VALUE;
int mini = 0;
for (int j = 1; j <= v; j++) {
if (!flag[j])
if (min > d[j]) {
min = d[j];
mini = j;
}
}
ans += min;
flag[mini] = true;
for (int j = 1; j <= v; j++)
if (!flag[j])
if (d[j] > map[mini][j]) {
d[j] = map[mini][j];
}
}
int min = Integer.MAX_VALUE;
for (int i = 1; i <= v; i++) {
if (min > map[0][i])
min = map[0][i];
}
System.out.println(min + ans);
}
}
}

 

 

 

 

 

 

 

 

这篇关于NYOJ38, 布线问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---