首页 > 数据结构 > Hash表 > POJ 2075 Tangled in Cables [解题报告] Java
2013
11-10

POJ 2075 Tangled in Cables [解题报告] Java

Tangled in Cables

问题描述 :

You are the owner of SmallCableCo and have purchased the franchise rights for a small town. Unfortunately, you lack enough funds to start your business properly and are relying on parts you have found in an old warehouse you bought. Among your finds is a single spool of cable and a lot of connectors. You want to figure out whether you have enough cable to connect every house in town. You have a map of town with the distances for all the paths you may use to run your cable between the houses. You want to calculate the shortest length of cable you must have to connect all of the houses together.

输入:

Only one town will be given in an input.
  • The first line gives the length of cable on the spool as a real number.
  • The second line contains the number of houses, N
  • The next N lines give the name of each house’s owner. Each name consists of up to 20 characters {a–z,A–Z,0–9} and contains no whitespace or punctuation.
  • Next line: M, number of paths between houses
  • next M lines in the form

< house name A > < house name B > < distance >

Where the two house names match two different names in the list above and the distance is a positive real number. There will not be two paths between the same pair of houses.

输出:

The output will consist of a single line. If there is not enough cable to connect all of the houses in the town, output

Not enough cable

If there is enough cable, then output

Need < X > miles of cable

Print X to the nearest tenth of a mile (0.1).

样例输入:

100.0
4
Jones
Smiths
Howards
Wangs
5
Jones Smiths 2.0
Jones Howards 4.2
Jones Wangs 6.7
Howards Wangs 4.0
Smiths Wangs 10.0

样例输出:

Need 10.2 miles of cable

解题代码:

//* @author: SmilingWang
import java.util.*;
public class Main {
  public static final int BLOCK = Integer.MAX_VALUE;
  public static final double zero = 1e-6;
  public static double cl;
  public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	cl = in.nextDouble();
	int pn = in.nextInt();
	double w[][] = new double[pn+1][pn+1];
	for(int i = 1; i <= pn; i++){
		for(int j = 1; j <= pn; j++){
			if(j == i){
				continue;
			}
			w[i][j] = BLOCK;
		}
	}
	Map< String, Integer> map = new HashMap< String, Integer>();
	for(int i = 1; i <= pn; i++){
		String s = in.next();
		map.put(s, i);
	}
	int en = in.nextInt();
	for(int i = 1; i <= en; i++){
		String s1 = in.next();
		String s2 = in.next();
		int i1 = map.get(s1);
		int i2 = map.get(s2);
		w[i1][i2] = in.nextDouble();
		w[i2][i1] = w[i1][i2];
	}
	prim(w, pn);
   }

   public static void prim(double[][] w, int n){
	int nearest[] = new int[n+1];
	double distance[] = new double[n+1];
	int vnear = 0;
		
	Set< Edge> set = new HashSet< Edge>();
	for(int i = 2; i <= n; i++){
		nearest[i] = 1;
		distance[i] = w[1][i];
	}
	for(int v = 2; v <= n; v++){
		double min = BLOCK;
		for(int i = 2; i <= n; i++){
		  if(distance[i] >= zero && distance[i] < min){
			vnear = i;
			min = distance[i];
		  }
		}
		Edge edge  = new Edge(nearest[vnear], vnear, w[vnear][nearest[vnear]]);
		set.add(edge);
		distance[vnear] = -1;
		for(int i = 2; i <= n; i++){
		   if(w[i][vnear] < distance[i]){
			distance[i] = w[i][vnear];
			nearest[i] = vnear;
		   }
		}
	}
	//System.out.println(set);
	Iterator< Edge> itr = set.iterator();
	double cost = 0;
	String out = "";
	while(itr.hasNext()){
		cost += (itr.next().weight);
	
	}
	//System.out.println(out);
	if(cost - cl <= zero){
		System.out.printf("Need %.1f miles of cable\n",cost);
	}
	else{
		System.out.println("Not enough cable");
	}
   }
}

class Edge{
	int sv;
	int ev;
	double weight;
	
	public Edge(int sv, int ev, double w){
		this.sv = sv;
		this.ev = ev;
		this.weight = w;
	}
	public String toString(){
		return sv + " " + ev + " " + weight + " ";
	}
}

  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience