yzmduncan
- 浏览: 326971 次
- 性别:
- 来自: 武汉
-
最新评论
-
di1984HIT：
学习了～
Spring scope="prototype" -
netkiller.github.com：
路还很长看看我的博客 http://netkiller.git ...
写博客是个好习惯 -
ooo456mmm：
JAVA 设计模式之——动态代理 -
hanmiao：
问题是这么问的：请使用 Java 的基本数据类型表示壹下单链表 ...
JAVA数据结构之——单链表的逆序 -
hanmiao：
谢谢，今天刚好有人问我这个问题，结果没有答上来，看了你这篇文章 ...
JAVA数据结构之——单链表的逆序
文章列表
考虑如下问题：
一个牧场由R*C个点组成。牧场内有若干条运输通道，通道流量上限是Ci，连接水平或者垂直相邻的的点。(1,1)内有很多干草，Farmer John希望将干草运送到点(R,C)。问最大流量是多少。1<R,C<=200。
...
考虑这样一个问题：
老师想通知他的所有学生一个消息，虽然他手上有他们的联系方式，但是一个一个联系太耗时间和电话费了。他知道其它人也有一些别人的联系方式，这样可以通知他人，再让他们去通知一下别人。现在要求出至少需要联系多少人，最少需要多少花费，使得所有的人都被通知到。
上述问题可以抽象为：图G中，每个点都有一个权值，若a能联系到b，则连边(a,b)。选出最少的点数(或者权值最小)，使从这些点能到达所有点。
解：求图G的强连通分量，入度为0的强连通分量个数即为最小点基，从每个入度为0的强连通分量中取出权值最小的点，构成的集合即最小权点基。求强连通Trajan算法 ...
比赛的时候知道是最小支配集问题，想到了用DLX，不过没能A掉。
题意：
街霸游戏中，有n种角色，每种角色有1~2种人物，比如说Ryu有两种人：Metsu Hadoke和Metsu Shoryuken。Ryu用Metsu Hadoke可以轻易打败Chun-Li，用Metsu Shoryuke可以打败Ken。从n种角色中选出哪些角色在那种人物上，可以击败其余的任何角色的任何人物。求选取的最少人物。
Dancing Links是Knuth教授在近几年来写的一篇文章，是一类搜索问题的通用优化。它主要利用双向十字链表来存储稀疏矩阵，来达到搜索中的优化。在搜索问题中，矩阵会随着递归的加深会变得越来越稀疏，这种情况下用dancelink ...
二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。在这个基础上，把每个点赋予一个非负的权值，这两个问题就转化为：二分图最小点权覆盖和二分图最大点权独立集。
二分图最小点权覆盖
从x或 ...
基础知识
欧拉回路是图G中的一个回路，经过每条边有且仅一次，称该回路为欧拉回路。具有欧拉回路的图称为欧拉图，简称E图。
无向图中存在欧拉回路的条件：每个点的度数均为偶数。
有向图中存在欧拉回 ...
最近开始学网络流了，原来或多或少接触过最简单的最大流问题：
一个公路网，每条公路都有一定的车载上限，问整个网络最大的车流量是多少。这个问题可以形式化为：
定义：给有向图G中的每一条弧(u,v)赋予一个值f(u,v)，并规定两个点s和t。如果除了s，t外的任意一个节点i，都有sum{f(u,i)}=sum{f(i,v)}。那么我们说f是一个流，并把s成为源(source)，t称为汇(sink)。并把上式称为流量平衡条件。
最大流问题
求有向图G中的一个流，它满足容量限制条件f(u,v)<=c(u,v)，且源点提供的流尽量大。
最小割最大流 ...
一. 指针
声明： int *a = 3; 声明了一个int类型的指针变量a，初始值为3。
赋值： int b = 3; a = &b; 将变量a的值(即地址)指向b，得到 *a == 3。
指针的好处：
1. 处理堆中存放的大量数据;
2. 快速访问类的成员数据和函数;
3. 以别名方式向函数传递参数。
const与指针：
指向常量的指针是指针的值(地址)可以修改，可以指向其它const对象，但指针所指向的对象不能修改。
如：
const double *a;
const double b = ...
2-SAT是求解一组逻辑变量表达式(avb)^(cvd)...(xvy)=1成立的问题，称为适定性问题(Satisfiability)，简称SAT。
对于逻辑表达式(xvy)，构造有向图G，也就是说，x和y至少选一个：如果不选x，肯定要选y；不选y，肯定要选x。在图G中添加两条有向边(~x,y)和(~y,x)。
对于逻辑表达式(x^y)，x和y都要选：若选x，则必选y(x,y)；选y，必选x(y,x)；不选x，则无解(~x,x)；不选y，则无解(~y,y)。
然后求图G的强连通分量，对于图中的任何一个强连通分量，如果我们选择其中的任何一个点，那么该SCC中所 ...
最小生成树的算法想必大家都很了解，主要有kruskal和prim。但如果要求次小生成树(即第二小的生成树)呢？
一种容易想到的方法是枚举删除最小生成树上的边，再求最小生成树。用kruskal这种算法的复杂度为O(n*elog2e)，当图比较稠密时，复杂度接近O(n^3)。
但有一种更简单的方法：先求最小生成树T，枚举添加不在T中的边，则添加后一定会形成环。找到环上边值第二大的边(即环中属于T中的最大边)，把它删掉，计算当前生成树的权值，取所有枚举修改的生成树的最小值，即为次小生成树。
这种方法在实现时有更简单的方法：首先求最小生成树T，然后从每个结点u遍历最 ...
有向图的强连通分量(strongly connected components)
在有向图G中，如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的路径，同时还有一条从vj到vi的路径(顶点相互可达)，则称两个顶点强连通。如果有向图G的每对顶点都强连通，称G是个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。
求解强连通分量的算法主要有三种：Kosaraju，Tarjan，Gabow。下面介绍Tarjan算法。
Tarjan算法基于图的深度遍历。定义dfn[u]是结点u的时间戳，low[u]为u和u的子树能够追溯到的最早的栈中结点的时间戳。
...
双连通图：在无向图连通图中，如果删除该图中的任意一点和依附它的边，不改变图的连通性，则称该图为双连通的无向图。
由上述定义可知，双连通分量中，每两个结点之间至少有两条不同的路径可以相互到达。
割点：在无向连通图中删去某个点a和依附a的边，图变为不连通，则该点称为割点，也叫关节点。
割边：在无向连通图中删去某条边，图变为不连通，则该边称为割边，也叫桥。
点双连通分支(块)与边双连通分支：
点双连通分支与边双连通分支是两个完全不同的概念。割点可以存在多个点连通分支中(相反，桥就不一样)。一个图可以有割点而没有割边，也可以有割边而没有割点。
点 ...
学习最小费用最大流前，需要学习最大流算法。在最大流算法中，没有考虑边的费用问题。在MinCostMaxFlow中，引入了费用的概念：cij表示边(i,j)单位流量的费用。在满足流量=v(f)的同时，并且要求费用最少。
最小费用最大流的迭代算法：
1.求出从s到t的最小费用通路(spfa)和通路的最大流量f。
2.让通路上的边(i,j)流量减去f；添加反向边(j,i)，容量为f，费用为-cost(i,j)。
3.重复1,2，直到从s到t的流量=v(f)或者再也找不到从s到t的最小费用道路为止。
最小费用最大流算法还可以解决二分图最优匹配。
...
如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如：xj-xi<=bk，其中，1<=i,j<=n, 1<=k<=m。则称其为差分约束系统(System of difference constraints)。差分约束系统就是求解关于一组变量的不等式组的方法。
...
后缀数组，很精妙的数据结构。
后缀：从母串的某一位置开始到结尾，suffix(i) = Ai,Ai+1...An。
后缀数组：后缀数组SA是个一维数组，它保存1...n的某个排列SA[1],SA[2]...SA[n]，并且保证suffix(SA[i])<suffix(SA[i+1])，也就 ...