发表于 | 分类于
字数统计: 917 字 | 阅读时长 ≈ 4 分钟

2.4.4 并查集

并查集的实现（交大《数据结构》教材中的实现）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int disjoint[500000]; //使用时别忘了先全部初始化为-1 
int find(int x)
{
	if(disjoint[x] < 0) return x;
	return disjoint[x] = find(disjoint[x]); //路径压缩
}

void Union(int root1, int root2)
{
	if(root1 == root2) return ;
	if(disjoint[root1] > disjoint[root2])// disjoint[root2]为负值，其绝对值为并查集的大小
	{
		disjoint[root2] += disjoint[root1];
		disjoint[root1] =root2;
	}
	else
	{
		disjoint[root1] += disjoint[root2];
		disjoint[root2] =root1;
	}
}
阅读全文 »

发表于 | 分类于
字数统计: 4,082 字 | 阅读时长 ≈ 18 分钟

2.3.1 记忆化搜索与动态规划

01 背包问题
有n个重量和价值分别为$w_i, v_i$的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。

循序渐进，先用最朴素的递归方法，针对每个物品是否放入背包进行搜索试试看。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n, W;
const int MAX_N = 10010;
int w[MAX_N], v[MAX_N];

//从index为i的物品开始挑选总重小于j的部分
int rec(int i,int j)
{
	int res;
	if(i==n) //没有剩余的物品了
	{
		res = 0;
	}
	else if(w[i]>j)//index为i的物品重量大于剩余总重
	{
		res = rec(i+1,j);
	}
	else
	{
		res = max(rec(i+1,j),rec(i+1,j-w[i]) + v[i]);
	}
	return res;
}

void solve()
{
    printf("%d\n", rec(0,W));
}

这种方法搜索深度为n，如第19行所示，每一层都有两个分支，那么最坏的复杂度为$O(2^n)$。因为会有相同参数的rec的多次调用，重复计算，耗时费神。故记忆化搜索的想法是把第一次计算的结果记录下来，之后直接调用以防重复计算。

阅读全文 »

发表于 | 分类于
字数统计: 1,214 字 | 阅读时长 ≈ 5 分钟

2.1.4 深度优先搜索

[http://poj.org/problem?id=2386]: “Lake Counting”

有一个大小为N*M的园子，雨后积了很多水。八连通的积水被认为是在一起的。请求出园子里共有多少个水洼？(八连通是指下图中相对.的8 部分)
www
w.w
www

从任意的’W’开始，不停地把邻接的部分用’.’代替，一次DFS(深度优先遍历)遍历后，与初始的这个 W 所连接的所有 ‘W’ 都会被替换成 ‘.’，因此直到图中没有 ‘W’为止，总共进行 DFS 的次数即为积水的次数。
使用深度优先搜索，从任意W开始，进入DFS，在DFS中把八联通的邻接部分都’.’代替，若八连通区域中又有一个”W”，进入下一层DFS，直到当前的连通分支不再有W，总共DFS的次数就是答案。八连通对应着8个方向的状态转移，每个格子至多调用一次DFS，所以复杂度是$O(8\times N \times M) = O(N \times M)$。

阅读全文 »