题意:
给出N个城镇的坐标和M条已经建好的路, 求连接所有城镇且长度之和最小的高速公路系统的每条公路, 已经存在的公路不用输出。
样例:
Sample Input
9 (城镇个数及坐标)
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3 //M条已建好的路,城镇1-->3,9--->7,1--->2
1 3
9 7
1 2
Sample Output
1 6
3 7
4 9
5 7
8 3
由于最后不用输出长度值, 而且坐标的绝对值不超过10000, 所以在算城镇距离的时候就直接省去了sqrt(),由于需要输出MST的边, 所以开了preVex[]记录每个结点的前驱结点, 默认值都为1. 每次选到新的扩展结点min_i后, 若连接它的边权值不为-1, 即这条路是新修建的, 则输出这条边. 然后如果min_i到MST外的某一结点i的权值, 比MST中其它结点到i的权值还要小, 那么更新dis[1][i]): dis[1][i]=dis[min_i][i], 然后顺带更新preVex[i]为min_i.
import java.util.Scanner;
public class Main{
private int dis[][];//邻接矩阵
private int n;//城镇的个数
private boolean vis[]; //城镇已加入到MST的标志
public Main(int n,int[][] dis){
this.n=n;
this.dis=dis;
vis=new boolean[n+1];
}
static int DIS(int x1,int y1,int x2,int y2){//计算两城镇的距离(权)
return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
private void prim(){
int preVex[]=new int[n+1];
vis[1]=true; //城镇1已加入到MST
for(int i=1;i<=n;i++) preVex[i]=1;
for(int k=1;k<n;k++){
int min_i=1;
int min = Integer.MAX_VALUE;
for(int i=1;i<=n;i++){
if(!vis[i] &&dis[1][i]<min) {
min=dis[1][i];
min_i=i;
}
}
vis[min_i]=true; //城镇min_i已加入到MST
if(dis[1][min_i]!=-1) System.out.printf("%d %d\n",preVex[min_i],min_i);
for(int i=1;i<=n;++i)
if(!vis[i] && dis[min_i][i]<dis[1][i]){
dis[1][i]=dis[min_i][i];
preVex[i]=min_i;
}
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[][] dis=new int[n+1][n+1];
int x[]=new int[n+1];
int y[]=new int[n+1];
for(int i=1;i<=n;i++){//n个城镇的坐标
x[i]=in.nextInt();
y[i]=in.nextInt();
}
int m=in.nextInt();//m条已建好的公路
int u,v;
for(int i=1;i<=m;++i){
u=in.nextInt();
v=in.nextInt();
dis[u][v]=dis[v][u]=-1; //城镇u与v之间已有公路,他们的距离设为-1,必进最小生成树
}
for(int i=1;i<n;++i) {
for(int j=i+1;j<=n;++j)
if(dis[i][j]==0)
dis[j][i]=dis[i][j]=DIS(x[i],y[i],x[j],y[j]);
}
new Main(n,dis).prim();
}
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1704752
北大POJ1789-Truck History【Prim】 解题报告+AC代码
NULL 博文链接:https://200830740306.iteye.com/blog/603493
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
北大POJ2485-Highways【Prim】 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
(3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) .....
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
POJ1048,加强版的约瑟夫问题 难度中等
度限制最小生成树代码 摘自POJ1639代码
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
Algorithm-Java Algorithms + Data Structures = Programs. ——Niklaus Wirth 没日没夜地写程序。看到这几个字我两眼一黑,仿佛这就是我未来的生活。 为了摆脱这种焦虑心理,我逐步...最小生成树(prim,kruskal)(p
最小度限制生成树的求法也不是很难,先把度被限制的那个点(s点)去掉,求一次MST,然后把s到各个连通分量的最小权值的边加上,然后继续加边看看能否使生成树权减小(详见解题报告)。
用java的biginteger实现的poj1001,比较简单的方法
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】