【最小生成树】道路建设 - 木东驿站 - Powered by MoodBlog

CONTENT

【最小生成树】道路建设

题目描述

随着如今社会的不断变化,交通问题也变得越来越重要,所以市长决定建设一些公路来方便各个城市之间的贸易和交易。虽然市长的想法很好,但是他也遇到了一般人也经常头疼的问题,那就是手头的经费有限……在规划过程中,设计师们已经预算出部分城市之间建设公路的经费需求。现在市长想知道,它能不能将他的m个城市在有限的经费内实现公路交通。如果可以的话,输出Yes,否则输出No(两个城市不一定要直接的公路相连,间接公路到达也可以。)

输入描述

测试输入包含多条测试数据
每个测试数据的第1行分别给出可用的经费c(<1000000),道路数目n(n<10000),以及城市数目m(<100)。
接下来的n行给出建立公路的成本信息,每行给出三个整数,分别是相连的两个城市v1、v2(0<v1,v2<=m)以及建设公路所需的成本h(h<100)。

输出描述

对每个测试用例,输出Yes或No。

示例输入

20 10 5

1 2 6

1 3 3

1 4 4

1 5 5

2 3 7

2 4 7

2 5 8

3 4 6

3 5 9

4 5 2

示例输出

Yes

博主代码

import java.util.Scanner;
public class Main{
	public static void main(String args[]){
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int S = scanner.nextInt();
			int SN = scanner.nextInt();
			int N = scanner.nextInt();
			
			Node[] nodes = new Node[N];
			for(int i=0;i<N;i++){
				nodes[i] = new Node();
			}
			for(int i=0;i<SN;i++){
				int a = scanner.nextInt()-1;
				int b = scanner.nextInt()-1;
				int t = scanner.nextInt();
				nodes[a].addNext(b, t);
				nodes[b].addNext(a, t);
			}
			int ans = Prim(nodes);
			if(ans<=S){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}			
		}
		
	}
	public static int Prim(Node[] nodes){
		int l = 0;
		int ans = 0;
		Node[] tnodes = new Node[999];
		tnodes[l++] = nodes[0];
		nodes[0].used = true;
		for(int i=1;i<nodes.length;i++){
			int min = 666666;
			int t = 0;
			for(int j=0;j<l;j++){
				for(int k=0;k<tnodes[j].l;k++){
					if(nodes[tnodes[j].next[k]].used==false&&tnodes[j].length[k]<min){
						min = tnodes[j].length[k];
						t = tnodes[j].next[k];
					}
				}
			}
			nodes[t].used = true;
			tnodes[l++] = nodes[t];
			ans+=min;
		}
		return ans;
	}
}
class Node{
	int l;
	int next[] = new int[999];
	int length[] = new int[999];
	boolean used = false;
	public void addNext(int n,int t){
		next[l] = n;
		length[l] = t;
		l++;
	}
}


个快快 2018年03月08日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号