POJ 2075 Tangled in Cables (c++/java)
题目大意:
给你一些人名,然后给你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) ; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。