128kj
- 浏览: 600483 次
- 来自: ...
-
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
文章列表
N阶楼梯上楼问题：一次可以走两阶或一阶，请把所有行走方式打印出来。
import java.util.Scanner;
public class Main{
private int n;
private int[] answer;//存入上楼梯的方法
private int ways;//上楼梯方法总数
public Main(int n){
this.n=n;
answer=new int[n+1];
}
public int getWays(){
return ways;
...
回溯法的基本做法是搜索解空间，一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。上文“回溯法入门学习之一”http://128kj.iteye.com/blog/1722216中已给出了一个框架：
"深度优先搜索+回溯"递归框架：
函数DFS（节点）{
如果（节点=目标节点） {找到目标，跳出}
遍历所有下一层节点for(int i=0;i<k;i++){
标记下一层节点i已访问;
DFS（下一层的节点i）
恢复i为未访问
}
}
下面使用上面框架再解一例（数独问题）:
题目大意,如上图(一):
...
一： 回溯法
有时我们要得到问题的解，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择， 然后继续向前试探，反复这样的过程直到求出问题的解。比喻:“下棋”： 每一次走棋的位置都要考虑到是否是损人利己，如果是害人害己的走法就要回撤，找下一步损人利己的走法。又如玩RPG游戏中碰到“迷宫”大家是怎样出来的?
回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点 ...
题:输出从n不同元素中取m个的所有组合
下面程序使用了深度优先搜索:
public class Combination{
private char a[]; //存储初始字符串
private char r[]; //存储组合结果
public Combination(char[] a){
this.a=a;
r=new char[a.length];
}
//n, 初始字符串的长度
//m, 所求组合的长度
//k, 初始集合中当前处理位置, a[k]
//index 组合的当前长度
void combination(int n, int m, i ...
POJ 3895
题意:
求最大环的边数,给出一个无向图,图中每条边的长度都是1,求图中最长环的长度是多少？
样例：
Sample Input
1 -------->这里是测试次数
7 8 ----------------->七个点，八条边
3 4 ---------------->顶点3到4有一条边
1 4
1 3
7 1
2 7
7 5
5 6
6 2
Sample Output
4
AC代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Sc ...
如图：求出有向图的所有环。
import java.util.ArrayList;
import java.util.Arrays;
public class TestCycle {
private int n;
private int[] visited;//节点状态,值为0的是未访问的
private int[][] e;//有向图的邻接矩阵
private ArrayList<Integer> trace=new ArrayList<Integer>();//从出发节点到当前节点的轨迹
privat ...
题（HDU2544）：
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。
接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000） ...
Dijkstra算法是用来解决：确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
它是常用的最短路径算法之一。最常用的路径算法有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。
缺陷： ...
很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路。
我们用数组dist记录每个结点的最短路径估计值，而且用邻接表(或邻接矩阵）来存储图G。采取的方法是动态逼近法：
设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作（看程序注释），如果v点的最短路径估计值有所调整， ...
Bellman-Ford算法：
为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。
Bellman-ford算法是求解连通带权图中单源 ...
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。
Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，Bellman－Ford算法可以大致分为三个部分:
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标 ...
题目大意:
输入一个数t，表示测试组数。然后每组第一行两个数字n,m，n表示有n只昆虫， 编号从1—n,m表示下面要输入m行交配情况，每行两个整数，表示这两个编号的昆虫为异性，要交配。 要求统计交配过程中是否出现冲突，即是否有两个同性的昆虫发生交配。
[输入输出]: [样例]:
Sample Input
2 （二次测试）
3 3(三条虫子，三对信息）
1 2
2 3
1 3
4 2(四条虫子,二对信息)
1 2
3 4
Sample Output
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs ...
拓扑排序简单来说就是把一个图的所有节点排序,使得每一条有向边(u,v)对应的u都排在v的前面。 拓扑排序最大的用途就是判断一个有向图是否有环。
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无 ...