http://poj.org/problem?id=2075

题目大意：

给你一些人名，然后给你n条连接这些人名所拥有的房子的路，求用最小的代价求连接这些房子的花费是否满足要求。

思路：

昨天20分钟的题，输入不小心写错了- -|||||看世界杯半场歇息随便看了下发现了。。。。T T

用map进行下标的映射，然后求MST就可以。

c++

#include<cstdio>

#include<string>

#include<map>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN = 500;

int fa[MAXN];

struct edge

{

	int from, to;

	double val;

	bool operator < (const edge& x)const

	{

		return val < x.val;

	}

}e[MAXN*MAXN];

map<string, int> m;

int find(int cur)

{

	return cur == fa[cur] ? cur : fa[cur] = find(fa[cur]);

}

int main()

{

	int len = 0, n;

	double a;

	cin >> a >> n;

	while (n--)

	{

		string temp;

		cin >> temp;

		m[temp] = len++;

	}

	cin >> n;

	for (len = 0; len<n; len++)

	{

		string from, to;

		double value;

		cin >> from >> to >> value;

		e[len].from = m[from];

		e[len].to = m[to];

		e[len].val = value;

	}

	for (int i = 0; i<len; i++)

		fa[i] = i;

	sort(e, e + len);

	double ans = 0;

	for (int i = 0; i<len; i++)

	{

		int from = e[i].from;

		int to = e[i].to;

		int root_x = find(from);

		int root_y = find(to);

		if (root_x == root_y) continue;

		fa[root_x] = root_y;

		ans += e[i].val;

	}

	if (ans >  a)

		printf("Not enough cable\n");

	else

		printf("Need %.1lf miles of cable\n", ans);

	return 0;

}

JAVA:

import java.math.BigDecimal;

import java.text.DecimalFormat;

import java.util.Arrays;

import java.util.Scanner;

import java.util.TreeMap;

public class Main {

	//final 相当于const

	public static final int MAXN=500;

	//写起来好不习惯

	public static int[] fa=new int[MAXN];

	public static TreeMap<String, Integer> m=new TreeMap<String, Integer>();

	public static edge[] e=new edge[MAXN*MAXN];

	public static int find(int cur)

	{

		//不能这么写？

		//return cur == fa[cur] ? cur : fa[cur] = find(fa[cur]);

		if(cur==fa[cur])

			return cur;

		else

			return fa[cur] = find(fa[cur]);

	}  

	public static void main(String[] args) {

		 int len = 0, n;

		 double a;  

		 Scanner in=new Scanner(System.in);

		 a=in.nextDouble();

		 n=in.nextInt();

		 while((n--)!=0)

		 {

			 String temp=in.next();

			 m.put(temp, new Integer(len++));

		 }

		 n=in.nextInt();

		 double value;

		 for (len = 0; len<n; len++)

		 {

		       String from=in.next();

		       String to=in.next();

		        value=in.nextDouble();

		        e[len]=new edge();

		        e[len].from = m.get(from);

		        e[len].to = m.get(to);

		        e[len].val = value;

		  }  

		 for (int i = 0; i<len; i++)

		        fa[i] = i;  

		//sort

		 Arrays.sort(e,0,len);

		 double ans=0;

		 for(int i=0;i<len;i++)

		 {

			  int from = e[i].from;

		      int to = e[i].to;

		      int root_x = find(from);

		      int root_y = find(to);

		      if (root_x == root_y) continue;

		      fa[root_x] = root_y;

		      ans += e[i].val;

		 }

		  if (ans >  a)

			  System.out.print("Not enough cable\n");

		    else

		      System.out.printf("Need %.1f miles of cable\n", ans);

		  //java 是.1f

	}

}

class edge implements  Comparable<edge>

{

	int from,to;

	double val;

	public int compareTo(edge x)

    {

		//double比較错了一次)

		BigDecimal data1 = new BigDecimal(this.val);

		BigDecimal data2 = new BigDecimal(x.val); 

        return data1.compareTo(data2) ;

    }

}