时间：2017.6.17
0x01搜索
一、定义
1.从数据集合中找出目标元素进行处理。
2.当我们难以通过分析解决给定问题,或者找不到一个能有效解决问题的算法时,就不得不依靠反复的试错来寻求问题的答案了。 而且在这里,可以用启发式搜索,即利用问题拥有的启发信息来引导搜索,达到减少搜索范围、降低问题复杂度的目的。二、对象
1.目的: 可以是需要进行处理的目标元素, 或者是答案本身。
2.类型: 可以是一个数值, 也可以是一个组合, 甚至可能可以是一个集合三、数值
类型: 线性, 二分, 散列
1.线性:从数组开头依次访问各元素,检查该元素是否与目标值相等。 线性搜索算法效率很低, 但是适用于任何形式的数据。
2.二分:通过不断不断缩小解存在的范围, 从而求得问题最优解的方法。 效率较高，应用较广。
3.散列:根据各元素的值来确定存储位置, 然后将位置保管在散列表中。 散列可以高效的执行动态插入，搜索，删除操作。四、组合
1.穷竭搜索：将所有的可能性罗列出来，在其中寻找答案。
2.迭代加深：对于可以用回溯求解但解答树的深度没有明显上限的题目。
3.状态空间搜索：找到一个从初始状态到终止状态的路径。
4.回溯法：将生成与检查有机的结合起来，实现剪枝。
5.A* IDA*：设计一个乐观的估价函数，实现剪枝。五、练习题 2017.6.5
尚未能包含大框架,
详细见具体知识点。0x02数据结构
一、基础
抽象数据类型(ADT):表(list,hash), 栈(stack), 队列(queue)
树相关(Tree):二叉树, 堆(heap)
库(STL):排序(sort), 集合(set), 映射(map)二、中级
树相关: 二叉搜索树, 线段树,
图相关: 并查集, 有向无环图(DAG), 0x03图论
图的基本概念：
一、图是什么
1.定义：图由顶点和边构成。顶点代表对象，边代表两个对象之间的连接关系。记为图G=(V(点集),E(边集));
2.应用：图被应用于解决错综的网状关系的问题当中。 往往可以用之建立相关的模型套入相关算法以解决问题。二、图的分类
1.依据一：边没有指向性的叫做无向图(朋友关系,路线图)，边具有指向性的叫做有向图(数值大小,流程图)。
2.依据二：根据边有无附加的属性(具有权值)，将图分为带权图，和不带权图。
3.依据三：根据图是否有环(从一个顶点出发经过若干边可以回到该顶点)分为有环图和无欢图。
4.依据四：任意两点之间都有路径的图叫做连通图，没有的叫非连通图。
5.典型的无向图：没有圈的连通图叫做树，没有圈的非连通图叫做森林。
6.典型的有向图：没有圈的有向图叫做DAG。三、图的表示
0.背景：图作为与线性不同的另一种新的数据结构类型，为了能够在程序中对之进行处理，需要将之按某种方法存储下来。
1.邻接矩阵：用一个二维数组表示(int e[maxn][maxn];)，e[i][j]表示顶点i与顶点j的距离，若不连通可以将之标记为inf。
2.邻接表一：用链表存储从顶点0出发有到顶点1,2,3的边(int first[maxn],next[maxn];)，其中first[i]表示顶点i出发的第一条边,next[i]表示边i的下一条边(可以用-1表示不存在)。
3.邻接表二：用向量存储从某顶点出发有到其余顶点的边(vector<int>G[maxn];)，其中G[i]存储了顶点i出发能够到达的其余边。图的相关算法(本节为大纲,具体参见详细算法整理)：
四、图的搜索
五、图的最短路
五、最小生成树
六、网络流
图相关的数据结构(本节已全部移至数据结构章节)
七、树
二叉树
最小堆
最大堆
并查集
线段树
AVL树
平衡树
红黑树
树套树
主席树
树状数组
二叉搜索树八、图
0x04DFS
一、定义
深度优先搜索算法（英语：Depth-First-Search，简称DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。二、基本框架(待修改)
1.访问顶点v
2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问
3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止三、用处
1.DFS求通块(因为能够遍历图, )
2.四、本章节相关专题建议阅读顺序
1.求通块
2.全排列
3.回溯法
4.练习题 2017.5.6
1.Codevs1294 全排列
2.Codevs1295 N皇后问题
3.Codevs3895 环素数
4.Codevs1983 等式问题
5.Codevs1018 单词接龙
6.Codevs1026 逃跑的拉尔夫 0x05最小生成树
一、讲道理
二、Kruscal
codevs1078
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, a[110][110], fa[110], co, ans;
struct side{
int u, v, w;
side (int u, int v, int w):u(u),v(v),w(w){}
bool operator < (const side b)const{ return w<b.w;}
};
vector<side>e;
int find(int x){ return x==fa[x]? x : fa[x]=find(fa[x]);}
int main(){
cin>>n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
int x; cin>>x;
if(i >= j)continue;
e.push_back(side(i, j, x));
}
}
sort(e.begin(), e.end());
for(int i = 1; i <= n; i++)fa[i] = i;
for(int i = 0; i < e.size(); i++){
if(find(e[i].u) != find(e[i].v)){
ans += e[i].w;
fa[find(e[i].u)] = find(e[i].v);
}
}
cout<<ans;
return 0;
}Codevs1231
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[100000];
int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]);}
struct L{ long long u, v, w; }e[100000];
bool operator < (const L A, const L B){ return A.w<B.w;}
int main(){
int n, m, count = 0;
long long ans = 0;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e,e+m);
for(int i = 0; i <= n; i++) fa[i] = i;
for(int i = 0; i <= m; i++){
if(find(e[i].u) != find(e[i].v)){
fa[find(e[i].u)] = e[i].v;
ans += e[i].w;
count++;
}
if(count == n-1)break;
}
printf("%lld
", ans);
return 0;
}三、Prim
0x06子集生成
问：生成0~n所有的子集。
答：
一、增量构造法
#include<iostream>
using namespace std;
int n, A[20];
void dfs(int cur){
for(int i = 1; i < cur; i++)cout<<A[i]<<" ";
cout<<"
";
int s = A[cur-1]+1;
for(int i = s; i < n; i++){
A[cur] = i;
dfs(cur+1);
}
}
int main(){
cin>>n;
A[0] = -1;
dfs(1);
return 0;
}二、位向量法
#include<iostream>
using namespace std;
int n, A[10];
void dfs(int cur){
if(cur == n){
for(int i = 0; i < n; i++)
if(A[i])cout<<i<<" ";
cout<<"
";
}else{
//A[cur] = 1;
dfs(cur+1);
A[cur] = 1;
dfs(cur+1);
A[cur] = 0;
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}三、二进制法
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
for(int i = 0; i < (1<<n); i++){
for(int j = 0; j < n; j++)
if(i&(1<<j))cout<<j<<" ";
cout<<"
";
}
return 0;
}0x07ADT抽象数据类型
一、定义
数据数据元素，数据关系以及相关的操作。二、内容
1. C++的Standard Template Library(模板库)
2. 图论算法的分装三、STL
<algorithm>
<vector>
<set>
<map>
<stack>
<queue>
<deque>
<list>
<utility>、<functional>、<iterator>、<array>、<forward_list>、<unordered_map>、<memory>、<numeric>、<unordered_set>、四、
0x08图的最短路径
一、例题(为形象理解,可无视)：
废话：
暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些之间则没有，为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之间的最短路径。
数据：//本例所有数据均针对有向无环图(DAG)
//代码看不懂的同学可以画一画样例数据的图的说。
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
//ans: 0 2 5 4
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
//ans:0 1 8 4 13 17
4 5
1 4 9
4 3 8
1 2 5
2 4 6
1 3 7
//ans:0 5 7 9
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//ans:0 -3 -1 2 4
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
//ans:0 2 5 9 9 二、Floyd-Wallshall
讲道理
本题Code
#include<iostream>
using namespace std;
int n, m, e[110][110];
const int inf = 0xffffff;
int main(){
cin>>n>>m;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
e[i][j] = i==j ? 0 : inf;
for(int i = 0; i < m; i++){
int a, b, c; cin>>a>>b>>c;
e[a-1][b-1] = c;
}
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(e[i][j] > e[i][k]+e[k][j])
e[i][j] = e[i][k]+e[k][j];
for(int i = 0; i < n; i++)cout<<e[0][i]<<" ";
return 0;
}三、dijkstra
讲道理
本题Code
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, d[110], book[110];
int e[110][110];
const int inf = 0xfffff;
int main(){
cin>>n>>m;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
e[i][j] = (i==j ? 0 : inf);
for(int i = 0; i < m; i++){
int a, b, c; cin>>a>>b>>c;
e[a-1][b-1] = c;
}
book[0] = 1;
for(int i = 0; i < n; i++)d[i] = e[0][i];
for(int i = 0; i < n; i++){
int x, y = inf;
for(int j = 0; j < n; j++)if(!book[j] && d[j]<y)y = d[x=j];
book[x] = 1;
for(int j = 0; j < n; j++)d[j] = min(d[j], d[x]+e[x][j]);
}
for(int i = 0; i < n; i++)cout<<d[i]<<" ";
return 0;
}优化的说
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, d[110], book[110];
int e[110][110];
int u[110], v[110], w[110], first[110], next[110]; //优化1：用邻接表代替邻接矩阵
const int inf = 0xfffff;
int main(){
cin>>n>>m;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
e[i][j] = (i==j ? 0 : inf);
for(int i = 1; i <= n; i++)first[i] = -1;
for(int i = 1; i <= m; i++){
cin>>u[i]>>v[i]>>w[i];
e[u[i]][v[i]] = w[i];
next[i] = first[u[i]];
first[u[i]] = i;
}
book[0] = 1;
for(int i = 2; i <= n; i++)d[i] = inf;
for(int i = 1; i <= n; i++){
int x, y = inf;
int k = first[i];
while(k != -1){
if(!book[u[k]] && d[u[k]]<y)y = w[x=u[k]];
k = next[k];
}
book[x] = 1;
for(int j = 1; j <= n; j++){
int k = first[x], t = inf;
while(k != -1){
if(v[k]==j){ t = w[k]; break;}
k = next[k];
}
if(d[j]>d[x]+t) d[j] = d[x]+t;
}
}
for(int i = 1; i <= n; i++)cout<<d[i]<<" ";
return 0;
}优化的说2
//优化2,3：向量存储+优先队列
四、bellman-ford
讲道理本题Code
#include<iostream>
using namespace std;
int u[110], v[110], w[110], d[110];
const int inf = 0xfffff;
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= m; i++)cin>>u[i]>>v[i]>>w[i];
for(int i = 2; i <= n; i++)d[i] = inf;
for(int k = 0; k < n; k++){
for(int i = 1; i <= m; i++)if(d[v[i]]>d[u[i]]+w[i])
d[v[i]] = d[u[i]]+w[i];
}
for(int i = 1; i <= n; i++)cout<<d[i]<<" ";
return 0;
}优化的说
#include<iostream>
using namespace std;
int u[110], v[110], w[110], d[110];
const int inf = 0xfffff;
int main(){
int n, m; cin>>n>>m;
for(int i = 1; i <= m; i++)cin>>u[i]>>v[i]>>w[i];
for(int i = 2; i <= n; i++)d[i] = inf;
for(int k = 0; k < n; k++){
int check = 1; //优化1：本次没有松弛操作，已经得到了最短路
for(int i = 1; i <= m; i++)if(d[v[i]]>d[u[i]]+w[i])
{ d[v[i]] = d[u[i]]+w[i]; check = 0;}
if(check)break;
}
for(int i = 1; i <= n; i++)cout<<d[i]<<" ";
int flag = 0;//功能1：检测负权回路
for(int i = 1; i <= m; i++)if(d[v[i]]>d[u[i]]+w[i])flag = 1;
if(flag)cout<<"flag was here
and this graph has the ---
";
return 0;
}五、bellman-ford
讲道理的说本题code
六、习题集
0x09漫水填充
一、题型分析
用于DFS求联通块二、例题
poj2486
题目(待翻译)：Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.
输入：
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出：
3//poj2386 - Lake Counting
#include<iostream>
#include<string>
using namespace std;
int n, m, ans;
string a[100];
void dfs(int x, int y){
for(int i = -1; i <= 1; i++)
for(int j = -1; j <= 1; j++)
if(x+i>=0&&x+i<n&&y+j>=0&&y+j<m && a[x+i][y+j]=='W')
{ a[x+i][y+j]='.'; dfs(x+i, y+j);}
}
int main(){
cin>>n>>m;
cin.get();
for(int i = 0; i < n; i++)getline(cin, a[i]);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(a[i][j] == 'W'){ dfs(i, j); ans++;}
cout<<ans<<"
";
return 0;
}UVa572
题目：输入一个m行n列的字符矩阵，统计“@”组成多少个八连通块。
输入：
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
输出：
2#include<iostream>
#include<string>
using namespace std;
int m, n; string a[110];
const int dx[] = {0,0,-1,1,-1,1,-1,1};
const int dy[] = {1,-1,0,0,-1,1,1,-1};
void dfs(int x, int y){
a[x][y] = '*';
for(int i = 0; i < 8; i++)
if(x+dx[i]>=0 && x+dx[i]<m && y+dy[i]>=0 && y+dy[i]<n && a[x+dx[i]][y+dy[i]]=='@')
dfs(x+dx[i],y+dy[i]);
}
int main(){
while(cin>>m>>n &&m &&n){
for(int i = 0; i < m; i++)cin>>a[i];
int ans = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(a[i][j] == '@'){ dfs(i,j); ans++;}
cout<<ans<<"
";
}
return 0;
}0x0A全排列问题
一、题目：
题目：给出一个n, 请输出n的所有全排列。
输入：
3
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1二、分析
1.
2.
3.三、提交
Codevs1294: http://codevs.cn/problem/1294/四、解答：
解法一、
#include<cstdio>
int n, a[10];
void dfs(int cur){
if(cur == n){
for(int i = 0; i < n-1; i++)printf("%d ", a[i]);
printf("%d
", a[n-1]);
}else for(int i = 1; i <= n; i++){
bool ok = true;
for(int j = 0; j < cur; j++)
if(a[j] == i)ok = false;
if(ok){
a[cur] = i;
dfs(cur+1);
}
}
}
int main(){
scanf("%d", &n);
dfs(0);
return 0;
}解法二、
#include<iostream>
using namespace std;
int n, a[20], book[20];
void dfs(int cur){
if(cur == n){
for(int i = 0; i < n; i++)cout<<a[i]<<" ";
cout<<"
";
}else for(int i = 1; i <= n; i++)if(!book[i]){
a[cur] = i;
book[i] = 1;
dfs(cur+1);
book[i] = 0;
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}