POJ 2075 Tangled in Cables (c++/java)

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) ;
    }
}