- 浏览: 37640 次
- 性别:
- 来自: 北京
最新评论
-
andyshar:
请问如何在现有的hadoop环境中安装?
Hadoop集群监控系统Ambari安装 -
qingtangpaomian:
失败123 写道您好楼主: 我装好之后为啥老是最后一 ...
Hadoop集群监控系统Ambari安装 -
失败123:
您好楼主: 我装好之后为啥老是最后一步Cluster ...
Hadoop集群监控系统Ambari安装
USACO - 3.1.1 - Agri-Net
原创文章转载请注明出处
摘要:Prim算法 , 图论
一. 题目翻译
1. 描述:
农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了使花费最少,他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。 每两个农场间的距离不会超过100000
2. 格式:
INPUT FORMAT:
第一行: 农场的个数,N(3<=N<=100)。
第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在80个字符,因此,某些行会紧接着另一些行。当然,对角线将会是0,因为不会有线路从第i个农场到它本身。
OUTPUT FORMAT:
只有一个输出,其中包含连接到每个农场的光纤的最小长度。
SAMPLE INPUT:
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
SAMPLE OUTPUT:
28
二. 题解
1. 题意理解(将问题分析清楚,大致用什么思路):
基本的Prim算法,按照算法实现的步骤来做就可以了。首先将起始点加入最小生成树中,然后遍历每次取最小的边加入,重复n-1次,就可以得到一颗完整的最小生成树。
2. 启示:
Prim算法是基本的图论算法,注意积累。
三. 代码
/*
ID:fightin1
LANG:JAVA
TASK:agrinet
*/
package session_3_1_1;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class agrinet {
public static void main(String[] args) throws Exception {
// Scanner in = new Scanner(System.in);
// PrintWriter pw = new PrintWriter(System.out);
Scanner in = new Scanner(new BufferedReader(new FileReader(
"agrinet.in")));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
"agrinet.out")));
ArrayList<Integer> now = new ArrayList<Integer>();//在最小生成树当中的节点
ArrayList<Integer> next = new ArrayList<Integer>();//不在最小生成树中的节点
int num = in.nextInt();
int[][] dist = new int[num][num];
for (int i=0;i<num;i++){
next.add(i);
for (int j=0;j<num;j++){
dist[i][j] = in.nextInt();
dist[j][i] = dist[i][j];
}
}
now.add(0);
next.remove(new Integer(0));
int cnt = 0;
for(int i=1;i<num;i++){
int min = Integer.MAX_VALUE;
int nextNode = -1;
for (int j=0;j<now.size();j++){
for (int k=0;k<next.size();k++){
if (dist[now.get(j)][next.get(k)]!=0){
if(dist[now.get(j)][next.get(k)]<min){
min = dist[now.get(j)][next.get(k)];
nextNode = next.get(k);
}
}
}
}
cnt = cnt + min;
now.add(nextNode);
next.remove(new Integer(nextNode));
}
// for (int i=0;i<num;i++){
// for(int j=0;j<num;j++){
// for(int k=0;k<num;k++){
// if (dist[j][i]+dist[i][k]<dist[j][k]){
// dist[j][k] = dist[j][i] + dist[i][k];
// }
// }
// }
// }
//
// int max = 0;
// for (int i=0;i<num;i++){
// for (int j=0;j<num;j++){
// if (dist[i][j]>max){
// max = dist[i][j];
// }
// }
// }
pw.println(cnt);
pw.close();
}
}
发表评论
-
USACO - 3.2.2 - Stringsobits
2012-08-23 16:02 805原创文章转载请注明 ... -
USACO - 3.2.1 - Factorials
2012-08-23 16:01 697原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 3.1.6 - Stamps
2012-08-23 16:01 1035原创文章转载请注明 ... -
USACO - 3.1.5 - Contact
2012-08-23 16:01 906原创文章转载请注明出处 摘要:二叉树的应用 , ... -
USACO - 3.1.3 - Humble Numbers
2012-08-23 16:00 710原创文章转载请注明 ... -
USACO - 3.1.2 - Score Inflation
2012-08-22 10:05 902原创文章转载请注明出处 摘要:动态规划 ... -
USACO - 2.4.5 - Fractions to Decimals
2012-08-22 10:04 958原创文章转载请注明出处 摘要:模拟 , 数论 ... -
USACO - 2.4.4 - Bessie Come Home
2012-08-22 10:04 903原创文章转载请注明出处 摘要:Dijkstra ... -
USACO - 2.4.2 - Overfencing
2012-08-22 10:03 998原创文章转载请注明 ... -
USACO - 2.4.1 - The Tamworth Two
2012-08-21 10:37 715原创文章转载请注明出处 摘要:模拟 ... -
USACO - 2.3.5 - Controlling Companies
2012-08-21 10:37 1299原创文章转载请注明出处 摘要:BFS , 模拟 ... -
USACO - 2.3.4 - Money Systems
2012-08-21 10:37 865原创文章转载请注明 ... -
USACO - 2.3.3 - Zero Sum
2012-08-21 10:36 741原创文章转载请注明出处 摘要:dfs , 枚举 ... -
USACO - 2.3.2 - Cow Pedigrees
2012-08-21 10:36 1007原创文章转载请注明 ... -
USACO - 2.3.1 - Longest Prefix
2012-08-20 20:31 1040原创文章转载请注明 ... -
USACO - 2.2.4 - Party Lamps
2012-08-20 20:30 1205原创文章转载请注明出处 摘要:枚举,三星 ... -
USACO - 2.2.3 - Runaround Numbers
2012-08-20 20:30 657原创文章转载请注明 ... -
USACO - 2.2.2 - Subset Sums
2012-08-20 20:30 693原创文章转载请注明出处 摘要:动态规划 ,0- ... -
USACO - 2.2.1 - Preface Numbering
2012-08-20 20:29 889原创文章转载请注明出处 摘要:模拟 , 数学分析 ... -
USACO - 2.1.5 - Hamming Codes
2012-08-18 19:22 779原创文章转载请注明出处 摘要:枚举、暴力 ...
相关推荐
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
此C++程序是实现了USACO网站上的Magic Squares的问题。
该题来自USACO,为最长串的查找,此处方法很笨,有更好方法
USACO chapter one.May hope it useful to someone
USACO chapter two.Useful for beginners.
usaco 上的题目barn1,beads,calfflac,可到那里查看具体题目
Notes-USACO-2021-弹簧
USACO-Cpp
C-Usaco-Work:Usaco在C中的工作
USACO-实践USACO 培训网站的工作实践代码! 100% 工作 - 大部分优化 - 混合语言
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
usaco3.1.1链式前向星+prim算法,pascal版
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案
USACO-TurtleCamera 该存储库包含我对USACO问题的所有解决方案。 CSE 199工作区目录将是我用来帮助开发USACO课程的主要目录。
我的USACO题解和程序
Java中的USACO金问题 YYMM 姓名 文件夹 笔记 代码 1812 美食 1812 牛适应性 1812 团队合作
USACO-Guide