- 浏览: 582940 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ1734
题意:给定一个N个点的无向图,求一个最小环(各边权值和最小的环)并输出路径。
样例:
Sample Input
5 7 (图有五个点,七条边)
1 4 1 (顶点1与4之间有一条边,权值为1,以下同)
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
思路:朴素的求法是:枚举每一条边(假设为e(i,j)),删除它,再求(i,j)之间的最短距离(用Dijkstra算法),该环就是dis(i,j) + e(i,j)。这样就需要依次枚举每条边,然后求一次最短路,时间复杂度为:O(N*N*M), 在N和M的数据规模较大时就会超时。
有一种改进的算法, 就是在求两点之间的最短路的时候,顺便求出最小环,即Floyd求最小环法。代码为:
该算法的证明:
一个环中的最大结点为K(编号最大),与其相连的两个点为i,j ,这个环的最短长度为: G[i][k] + G[k][j ] + i到j的路径中所有结点编号都不大于k的最短路径长度,根据floyd的原理,在最外层循环做一个k-1次之后, dis[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。
源码:
题意:给定一个N个点的无向图,求一个最小环(各边权值和最小的环)并输出路径。
样例:
Sample Input
5 7 (图有五个点,七条边)
1 4 1 (顶点1与4之间有一条边,权值为1,以下同)
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
思路:朴素的求法是:枚举每一条边(假设为e(i,j)),删除它,再求(i,j)之间的最短距离(用Dijkstra算法),该环就是dis(i,j) + e(i,j)。这样就需要依次枚举每条边,然后求一次最短路,时间复杂度为:O(N*N*M), 在N和M的数据规模较大时就会超时。
有一种改进的算法, 就是在求两点之间的最短路的时候,顺便求出最小环,即Floyd求最小环法。代码为:
void Floyd(){ for(int k=1;k<=N;k++){//环中的最大结点编号 for(int i=1;i<k;i++){//依次枚举k两端的结点 i , j for(int j=i+1;j<k;j++){ ans = MIN(ans, dis[i][j] + G[i][k] + G[k][j]);//最大节点为k的环的最短路径 } } for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ dis[i][j] = MIN(dis[i][j] , dis[i][k] + dis[k][j]); } } } }
该算法的证明:
一个环中的最大结点为K(编号最大),与其相连的两个点为i,j ,这个环的最短长度为: G[i][k] + G[k][j ] + i到j的路径中所有结点编号都不大于k的最短路径长度,根据floyd的原理,在最外层循环做一个k-1次之后, dis[i][j] 则代表了i到j的路径中所有结点的编号都不大于k的最短路径。
本题的代码: import java.util.Scanner; public class Main{ static final int INF = 0x3f3f3f3f ; private int n; //顶点数 private int[][] maze; //邻接矩阵 private int[][] dis; //dis[][]保存可以达到的最短距离,会变化; private int[][] fa; //标记(i,j)最短路径上,距离j最近的那个结点 private int[] res;//保存最小环的路径 private int temp; public Main(int n,int[][] fa,int[][] maze){ this.n=n; this.fa=fa; this.maze=maze; dis=new int[n+1][n+1]; res=new int[n+1]; } private void solve(int i, int j ,int k){//记录最小环的路径 temp = 0 ; while(j != i){ res[temp++] = j ; j = fa[i][j] ; } res[temp++] = i ; res[temp++] = k ; } private void Floyd(){ //Floyd求任意两点i,j之间的最短距离dis[i][j] for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dis[i][j] = maze[i][j] ; } } int ans = INF ; for(int k=1;k<=n;k++){ for(int i=1;i<k;i++){ for(int j=i+1;j<k;j++){ if(dis[i][j]<INF && maze[i][k]<INF && maze[k][j]<INF && ans>dis[i][j] + maze[i][k] + maze[k][j]){ ans = dis[i][j] + maze[i][k] + maze[k][j] ; //最大节点为k的环的最短路径 solve(i,j,k); //记录环的各顶点 } } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(dis[i][k]<INF && dis[k][j]<INF && dis[i][j]>dis[i][k] + dis[k][j]){ dis[i][j] = dis[i][k] + dis[k][j] ; fa[i][j] = fa[k][j] ; fa[j][i] = fa[k][i] ; } } } } if(ans == INF){ System.out.printf("No solution.\n"); } else{ for(int i=0;i<temp;i++){ System.out.printf("%d%c",res[i],i==temp-1?'\n':' '); } } } public static void main(String args[]){ Scanner in=new Scanner(System.in); int a ,b ,c ; while(in.hasNext()){ int n=in.nextInt();//顶点数 int m=in.nextInt();//边数 int maze[][]=new int[n+1][m+1]; int fa[][]=new int[n+1][n+1]; for(int i=1;i<=n;i++){ //初始化图 for(int j=1;j<=m;j++){ if(i == j) maze[i][j] = 0; else maze[i][j] = INF ; } } for(int i=1;i<=m;i++){ a=in.nextInt();//边的一端 b=in.nextInt();//边的另一端 c=in.nextInt();//边的权 if(maze[a][b] > c){ //重边取权小的 maze[a][b] = maze[b][a] = c ; fa[a][b] = a ; //标记(i,j)最短路径上,距离j最近的那个结点 fa[b][a] = b ; } } Main ma=new Main(n,fa,maze); ma.Floyd() ; } } }
源码:
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1522POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2403//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1837经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9546如图:求出有向图的所有环。 import java.uti ... -
三种算法(Floyd、Dijkstra、SPFA)求单源点最短路径。
2012-11-05 13:15 1774题(HDU2544): 在每年的校赛里,所有进入决赛 ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1297Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1864很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5813Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1395Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1349题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1529拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3981一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1782无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4960prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5351为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6213Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9023单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5465当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2588算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
判断图中是否存在环,无向图5分,有向图10分 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) 13、求...
图论中的圈与块,无向图的最小环 桥,割点,最小环 有向图的强连通分量
请输出无向连通图最小生成树权重之和。 输入: 第一行是2个整数,分别表示顶点个数n和边数m。接下来的m行中,每一行第一个整数表示边的开始顶点,第二个表示边的结束顶点,第三个表示这条边的权重。 ( 测试数据中保证...
8、 判断图中是否存在环,无向图5分,有向图10分 9、 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) ...
请输出无向连通图最小生成树权重之和。 输入 第一行是2个整数,分别表示顶点个数n和边数m。接下来的m行中,每一行第一个整数表示边的开始顶点,第二个表示边的结束顶点,第三个表示这条边的权重。 ( 测试数据中保证图...
有8个结点的无向图最多有 条边。 A.14 B. 28 C. 56 D. 112 ( C )4. 有8个结点的无向连通图最少有 条边。 A.5 B. 6 C. 7 D. 8 ( C )5. 有8个结点的有向完全图有 条边。 A.14 B. 28 C. 56 D. 112 ( B ...
求图的深度优先或广度优先的生成树(或生成森林)(存储结构为孩子-兄弟链表),并对生成树进行遍历(7、 判断图的连通性,输出连通分量的个数8、 判断图中是否存在环,无向图 9、 给出顶点u和v,判断u到v是否存在...
8、 判断图中是否存在环,无向图5分,有向图10分 9、 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) ...
18.下图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序列是( ① ),而进行广度优先遍历得到的顶点序列是( ② )。【中科院软件所 1999 六、2-(1)(2分)】 ①.A.1354267 B.1347652 ...
1.掌握建立无向图(有向图)的邻接矩阵和邻接表算法。 2.掌握无向图的深度优先遍历和广度优先遍历算法。 3.理解连通图的最小生成树算法(普里姆算法)。 4.理解有向无环图的拓扑排序算法。 二、实验内容 1.图的...
判断图中是否存在环,无向图5分,有向图10分 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) 13、求...
无向图 C.AOV网 D.AOE网 2.在边表示活动的AOE网中,关键活动的最迟开始时间( ) 最早开始时间。 A.> B.< C.>= D.= 3.带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中( ) 。 A.第i行非∞...
理解快速生成树协议的配置及原理。使网络在有冗余链路的情况下避免环 路的产生,避免广播风暴等。
3 最小路径覆盖问题 有向无环图最小路径覆盖 网络最大流 4 魔术球问题 有向无环图最小路径覆盖 网络最大流 5 圆桌问题 二分图多重匹配 网络最大流 6 最长递增子序列问题 最多不相交路径 网络最大流 7 试题库问题 ...
无向图求桥 无向图求割点 二分图匹配 匈牙利算法 Hopcroft-Karp算法 二分图最优匹配 KM 算法 最小树形图 朱刘算法 最大密度子图 01分数规划 && 网络流 无向图全局最小割 度数限制的最小生成树 最小直径生成树 最优...
用局部搜索算法,求一个无向图的最小生成树。 生成一个无向连通图,有100个点,1000条边,边上权重是1大20之间的随机整数。 局部搜索算法的基本思路: 1. 自己设法的到一棵生成树T 2. 检查不在T上的边,如果加上一...
一、实验目标1.掌握建立无向图(有向图)的邻接矩阵和邻接表算法。2.掌握无向图的深度优先遍历和广度优先遍历算法。3.理解连通图的最小生成树算法(普里姆算法)。4.理解有向无环图的拓扑排序算法。
因此,它首先使用最大最小父子节点 (MMPC) 算法构建 DAG(有向无环图)的骨架。 之后,它使用贝叶斯狄利克雷似然等价统一分数引导顶点之间的边。 有关更多信息,请阅读所附报告或*最大-最小爬山贝叶斯网络结构学习...
对有向无环图中具有长度约束的最大不相交路径问题进行研究,该问题是求解图中两点间路径长度为 k的最大不相交路径。为了对该问题进行求解,提出了贪婪搜索算法(GP,greedy path),该算法先将一个有向无环图转化为一棵...