HDU 1233 还是畅通工程
还是畅通工程
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20128 Accepted Submission(s): 8936
Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省易做图“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
方法一：Kruskal(克鲁斯卡尔)算法
第一步:排序
第二步：并查集算法
import java.io.*;
import java.util.*;
/*
* @author denghuilong
*
* 2013-8-8上午12:41:03
*
*/
public class Main {
public static ArrayList<Path> ay;
private static int[] patten;
public static int n,m;
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
while(sc.hasNextInt()){
n=sc.nextInt();
if(n==0) break;
m=n*(n-1)/2;
ay=new ArrayList<Path>();
for(int i=1;i<=m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int d=sc.nextInt();
Path p=new Path(a, b, d);
ay.add(p);
}
Kruskal();
}
}
//Kruskal(克鲁斯卡尔)算法
public static void Kruskal(){
//排序
Collections.sort(ay);
int count=0;
patten=new int[n+1];
//并查集 初始化
for(int i=1;i<=n;i++){
patten[i]=i;
}
int i=0;
//并查集 查找
for(int j=0;j<m;j++) {
int jj = patten[ay.get(j).a];
int kk = patten[ay.get(j).b];
if (jj != kk) {
i++;
count += ay.get(j).d;
union(jj, kk);
}
}
if(i!=n-1)
System.exit(0);
System.out.println(count);
}
// 并查集 合并
public static void union(int j, int k) {
for (int i = 1; i <= n; ++i) {
if (patten[i] == j) {
patten[i] = k;
}
}
}
}
class Path implements Comparable<Path>{
int a;
int b;
int d;
Path(int a,int b,int d){
this.a=a;
this.b=b;
this.d=d;
}
public int compareTo(Path o) {
return this.d>o.d?1:(this.d==o.d?0:-1);
}
}
方法二：Prim（普里姆算法）
算法思想：可取图中任意一个顶点V作为生成树的根，之后若要往生成树上添加顶点W，则在顶点V和W之间必定存在一条边。并且该边的权值在所有连通顶点V和W之间的边中取值最小。
一般情况下，假设n个顶点分成两个集合：U（包含已落在生成树上的结点）和V-U（尚未落在生成树上的顶点），则在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
import java.io.*;
import java.util.*;
/*
* @author denghuilong
*
* 2013-8-8上午12:52:40
*
*/
public class T1233 {
public static int n,m;
public static int M=102;
public static int MAX=Integer.MAX_VALUE;
public static int map[][]=new int[M][M];
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
while(sc.hasNextInt()){
n=sc.nextInt();
if(n==0) break;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=MAX;
}
}
m=(n-1)*n/2;
for(int i=0;i<m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int d=sc.nextInt();
if(map[a][b]>d){
map[a][b]=map[b][a]=d;
}
}
getDistance();
}
}
//Prim（普里姆算法）
public static void getDistance(){
int k=0,sum=0;
int dis[]=new int[n+1];
int mark[]=new int[n+1];
for(int i=2;i<=n;i++){
dis[i]=map[1][i];//初始化从起点到其他点之间的距离
mark[i]=0;
}
mark[1]=0;
//循环n-1次
for(int i=1;i<=n;i++){
int min=MAX;
//每次寻找最短的边
for(int j=2;j<=n;j++){
if(mark[j]==0&&dis[j]<min){
min=dis[j];
k=j;
}
}
if(min==MAX) break;
mark[k]=1;
sum+=dis[k];
// 到了一个新的点，重新计算它到其他点之间的距离
for(int j=2;j<=n;j++){
if(mark[j]==0&&dis[j]>map[k][j]){
dis[j]=map[k][j];
}
}
}
System.out.println(sum);
}
}
补充：软件开发 , C++ ,
