湖南平台网站建设企业,宁波网站建设-中国互联,外贸平台网站的营销方式,ps网站建设设计http://poj.org/problem?id2075 题目大意#xff1a; 给你一些人名#xff0c;然后给你n条连接这些人名所拥有的房子的路#xff0c;求用最小的代价求连接这些房子的花费是否满足要求。 思路#xff1a; 昨天20分钟的题#xff0c;输入不小心写错了- -|||||看世界杯半场休… http://poj.org/problem?id2075 题目大意 给你一些人名然后给你n条连接这些人名所拥有的房子的路求用最小的代价求连接这些房子的花费是否满足要求。 思路 昨天20分钟的题输入不小心写错了- -|||||看世界杯半场休息随便看了下发现了。。。。T T 用map进行下标的映射然后求MST即可。 c #includecstdio
#includestring
#includemap
#includealgorithm
#includeiostream
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];
mapstring, 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; lenn; 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; ilen; i)fa[i] i;sort(e, e len);double ans 0;for (int i 0; ilen; 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);elseprintf(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 相当于constpublic static final int MAXN500;//写起来好不习惯public static int[] fanew int[MAXN];public static TreeMapString, Integer mnew TreeMapString, Integer();public static edge[] enew edge[MAXN*MAXN];public static int find(int cur){//不能这么写//return cur fa[cur] ? cur : fa[cur] find(fa[cur]); if(curfa[cur])return cur;elsereturn fa[cur] find(fa[cur]); } public static void main(String[] args) {int len 0, n; double a; Scanner innew Scanner(System.in);ain.nextDouble();nin.nextInt();while((n--)!0){String tempin.next();m.put(temp, new Integer(len)); }nin.nextInt();double value; for (len 0; lenn; len) { String fromin.next();String toin.next();valuein.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; ilen; i) fa[i] i; //sortArrays.sort(e,0,len); double ans0;for(int i0;ilen;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 Comparableedge
{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) ; }
}转载于:https://www.cnblogs.com/murmured/p/5004026.html
