首页 > 代码库 > POJ 2075 Tangled in Cables (c++/java)
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=http://www.mamicode.com/in.nextDouble();>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。