hdu 5067 Harry And Dig Machine tsp问题

缘起

学习经典的 TSP 问题的N种姿势. 即售货商问题（又叫做中国邮政问题,或者货郎担问题）.

TSP是著名的NP问题,并且所有其他NP问题可以(在多项式时间)内约化(reduce)到TSP问题上来

hdu 5067 Harry And Dig Machine

TSP是著名的NP完全问题. 已经被证明无法给出多项式时间的算法.但是竞赛中依旧可能出现数据范围较小的题目.

Read More

区域的个数 坐标离散化

缘起

离散化是一种常用的技巧. 这里使用二维离散化技巧处理下面的问题（这是道好题，但是没找到地方提交 QAQ~）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
w*h(1<=w,h<=1e6)的格子上画了n(1<=n<=500)条垂直或者水平的宽度为1的直线. 
求出这些线将格子划分成了多少个区域.

【输入格式】 
第一行包含两个整数：w和h，表示矩阵的列数和行数（行列编号都从1开始）。 
第二行包含一个整数n，表示有n条直线。 
接下来的n行，每行包含四个整数：x1,y1,x2,y2，表示一条直线的列号和行号。

【输出格式】 
一个整数，表示区域数量。

【输入样例】
10 10
5
1 4 6 4
1 8 10 8
4 1 4 10
9 1 9 5
10 6 10 10

【输出样例】
6

Read More

二进制状态压缩

缘起

状态压缩是算法中常用的手段. 经常会联合dp、搜索中使用. 就拿搜索来讲，使用dfs毫无疑问，无论从空间复杂度还是性能上都不如直接枚举二进制数来得快（代价是不易读）.

所以有必要单独写篇文章来论述.

Read More