HJのBLOG

Mathematical knowledge

 Note  3336  7 分钟

质数

试除法判定质数
1
2
3
4
5
6
7
8

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}
……
阅读更多 »

Search and Graph Theory

 Note  3156  7 分钟

树与图的存储

树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a] [b]存储边a->b

(2) 邻接表：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;


// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);
……
阅读更多 »

Ds

 Note  2349  5 分钟

链表与邻接表：树与图的存储

单链表
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}
……
阅读更多 »