Command-Line Todo – t

t 是我最近在网上看到推荐的一个todo工具,它比较另类,不同于常规的todo app是基于web或client的,而是在Command-Line上的一个工具,这个todo工具让我眼睛一亮,就像当年看到 Octopress 一样。

 

以前用过Wunderlist,RTM,最近都一直用的是Any.do,挺简洁的一款todo app,Chrome上有插件,唯一一点不爽的就是基于网速的原因(也可能是其他原因),有时点了图标,但是半天才出来todo list,或者有时就出不来,这样的感觉太难受了。而我的工作环境是VMware下Gentoo终端里,自然更倾向于一些可以本地保存的命令行工具,所以 t 非常符合我。

 

继续阅读Command-Line Todo – t

最大流 — Edmond Karp算法

Edmond Karp算法的大概思想:

反复寻找源点s到汇点t之间的增广路径,若有,找出增广路径上每一段[容量-流量]的最小值delta,若无,则结束。

在寻找增广路径时,可以用BFS来找,并且更新残留网络的值(涉及到反向边)。

而找到delta后,则使最大流值加上delta,更新为当前的最大流值。

(粗体表明需要掌握的概念)

继续阅读最大流 — Edmond Karp算法

Huffman树简单总结+代码(C/C++)

Huffman树,中文霍夫曼树或哈夫曼树,又称最优二叉树,是一种带权路径长最短的树。

  • Huffman树的构建思想:

1.从原始元素集合T中拿出两个频度最小的元素组成一个二叉树,二叉树的根为这两个节点频度的和。

2.然后从集合T中删除这两个元素,把根元素加入到T集合中,如此反复直集合T为空。

  • 构建此过程的数据结构:

1.优先级队列

2.顺序存储结构

3.二叉链表(本文所用)

  • 逐步分析:

1.Huffman树的结构(二叉链表表示):

1
2
3
4
5
6
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表

2.SelectMin函数用于筛选最小的两个数,其中s1用于保存最小的,置于左孩子结点,s2保存第二小的,置于右孩子结点:

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
28
29
30
31
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}

3.最后的HaffmanCoding:

可以分为三部分,分别是Huffman树的初始化,创建,以及编码
代码里已经详细注释了:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}
  • 完整代码:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
 * Tanky Woo
 * Blog: www.WuTianQi.com
 * Description: Huffman Tree
 * Date: 2011.12.3
*/
#include <iostream>
using namespace std;
 
int m, s1, s2; // m是总结点个数,s1,s2用于筛选出最小和第二小的两个数
 
typedef struct{
    unsigned int weight;
    unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
 
typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表
 
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode);
 
int main()
{
    HuffmanTree HT;   // 哈夫曼树
    HuffmanCode *HC;  // 保存哈夫曼编码
    int *w, nNode, i; // w记录权值
    puts("输入结点数: ");
    scanf("%d", &nNode);
    HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode));
    w = (int *) malloc (nNode * sizeof(int));
    printf("输入 %d 个结点的权值\n", nNode);
    for(i = 0; i < nNode; i++)
        scanf("%d", &w[i]);
    HuffmanCoding(HT, HC, w, nNode);
    puts("\n各结点的哈夫曼编码:");   
    for(i = 1; i <= nNode; i++)
        printf("%2d(%4d):%s\n", i, w[i-1], HC[i]);
    getchar();
}
 
//选出weight最小的两个结点,s1保存最小的,s2保存第二小的
void SelectMin(HuffmanTree HT, int nNode)
{
    int i, j;
    for(i = 1; i <= nNode; i++)
        if(!HT[i].parent)
        {
            s1 = i;
            break;
        }
    for(j = i+1; j <= nNode; j++)
        if(!HT[j].parent)
        {
            s2 = j;
            break;
        }
 
    for(i = 1; i <= nNode; i++)
        if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
            s1 = i;
    for(j = 1; j <= nNode; j++)
        if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
            s2 = j;
    // 以上只筛选出最小的两个,这里保证s1的weight比s2的小
    if(HT[s1].weight > HT[s2].weight)
    {
        int tmp = s1;
        s1 = s2;
        s2 = tmp;
    }
}
 
// w[]存放nNode个字符的权值(均大于0),构造哈夫曼树HT,
// 并求出nNode个字符的哈夫曼编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
{
    int i, j;
    char *hfcode;
    int p;
    int cdlen;
    if(nNode < 1)
        return;
    m = 2*nNode-1;   //哈夫曼树的结点数
 
    /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
    HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
    for(i = 1; i <= nNode; i++)    //初始化
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    for(i = nNode+1; i <= m; i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
 
    puts("\n哈夫曼树的构造过程如下所示: ");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i = 1; i <= nNode; i++)
        printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
 
    printf("按任意键,继续...");
    getchar();
 
    /////////////////////////////以下是求Huffman树的构建/////////////////////////////
    for(i = nNode+1; i <= m; i++)
    {
        // 建立哈夫曼树
        // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
        // 其序号分别是s1和s2
        SelectMin(HT, i-1);
        HT[s1].parent = i;
        HT[s2].parent = i;
        cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
        printf("结点 weight parent lchild rchild");
        for(j = 1; j <= i; j++)
            printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
        printf("按任意键,继续...");
        getchar();
    }
 
 
    /////////////////////////////以下是求Huffman树的编码/////////////////////////////
    // 可以看看算法导论上对于DFS求路径的方法,分三色:白,灰,黑,这里weight=0,1,2和那里思想是类似的
    // 可以拿7,5,2,4这组数据来模拟下面的过程,以求更简单理解
    // 从根出发
    //递归遍历哈夫曼树,求哈夫曼编码
    hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
    p = m;
    cdlen = 0;
    for(i = 1; i <= m; i++)
        HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
 
    while(p)        //退出条件:p = 结点m的parent,即为0
    {
        if(HT[p].weight == 0)   //向左
        {
            HT[p].weight = 1;
            if(HT[p].lchild != 0)
            {
                p = HT[p].lchild;
                hfcode[cdlen++] = '0';
            }
            else if(HT[p].rchild == 0)
            {
                HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
                hfcode[cdlen] = '\0';   //保证后面的不会被复制
                strcpy(HC[p], hfcode);   //复制编码
            }
        }
        else if(HT[p].weight == 1)   //向右
        {
            HT[p].weight = 2;
            if(HT[p].rchild != 0)
            {
                p = HT[p].rchild;
                hfcode[cdlen++] = '1';
            }
        }
        else
        {
            // HT[p].weight == 2 退回到父结点,编码长度减一
            HT[p].weight = 0;
            p = HT[p].parent;
            --cdlen;
        }
    }
}

欢迎大家一起探讨。

  • 参考资料:

严蔚敏《数据结构》

最后给出一个题目:
http://acm.hdu.edu.cn/showproblem.php?pid=1053
HuffmanTree的题目,不过没用到求具体编码,所以相对要简单多了。
结题报告:

HDU/HDOJ 1053 Entropy (Huffman树)


http://www.cnblogs.com/Open_Source/archive/2010/07/10/1904936.html(STL优先级队列做法)

谈一下ACM的入门书籍及方法

首先说一下,ACM的入门方法多种多样,大部分人还是跟着学校一起参加集训,所以我这里主要是想对那些准备ACM入门的业余的朋友谈的。

入门书籍

首先推荐一些ACM的书籍:
(以下我都会给出在当当网的页面,方便大家直接购买,以下排名不分先后)

  • 1.《程序设计导引及在线实践》

http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub
这是我的第一本入门书,这本书是配套北大的百炼习题,注意不是POJ,貌似是北大内部测试用的,不过也是对外开放的,去年好像百炼变化过,所以不知道这本书还适不适合那个新的百炼系统。

  • 2.《算法竞赛入门经典》

http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub
这本书没话说,刘汝佳的白书,经典的算法入门书籍。强烈推荐!

  • 3.《算法艺术与信息学竞赛》

http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub
刘汝佳的黑书,难度较深,题目基本来至Uva,我是看了前面以部分,后面就没咋看了。。。

  • 4.《算法导论》

http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub
经典的书籍是不需要解释的。
这是我曾经上传过的英文版CHM算法导论,可以下载了看看:
http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA
我最近也在写算法导论的读书总结,欢迎大家探讨:
http://www.wutianqi.com/?p=2403

  • 5.《编程之美》

http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub
挺有意思的,不能作为一个算法的全面书籍,而是作为一本拓宽思维的书籍,有兴趣的建议要看看。

  • 6.《计算机程序设计艺术》

http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub
有好几卷的,只给出一卷的连接,而且网上版本很多,大家可以自行选择。
这个还没看,关键是没时间了,准备考研完了就趁着假期看完。

  • 7.《组合数学》

http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix
鸽巢原理,博弈,容斥原理,Catalan数等都属于这个范畴的,建议看看。

  • 8.《数据结构(C语言版)》严蔚敏

http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub
数据结构,这个必须得学好啊~~~

  • 9.《数据结构与算法分析C++描述(第三版)》

http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub
有时间可以看看,C++ Template写的,可以顺便巩固下template。

 

以下基本都没看过,不过貌似很有名,给出书名和连接:

  • 10.《世界大学生程序设计竞赛(ACM/ICPC)高级教程.第一册.程序设计中常用的计算思维方式》

http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub
这本我其实买了,但是还没有时间看。

  • 11.《国际大学生程序设计竞赛指南—ACM程序设计》

http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub

  • 12.《国际大学生程序设计竞赛例题解(三)图论、动态规划算法、综合题专集》

http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub
这个好像也有好几册,每一册都是单独讲一个方面的。

  • 13.《挑战编程:程序设计竞赛训练手册》

http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub

(作者:Tanky Woo, 个人博客:http://www.wutianqi.com ,C++/算法论坛:http://www.cppleyuan.com/ 。转载请注明个人及原文连接,谢谢合作)

入门方法
这么多书,不可能全部都看的,我觉得前10本,也就是我看过的,都还不错,大家可以看看。
另外,我个人推荐ACM可以这样入门(以下用到了上面书籍前面的序号):(当然,如果学校有专门培训的,则跟着学校来更好)

1.数据结构是基础,建议先把8号严蔚敏老师的《数据结构》好好看1~2遍,代码都手动敲一敲。
2.再看2号刘汝佳的白书
3.去年暑假(2010.7~2010.9月),我曾经给我的论坛(C++奋斗乐园:http://www.cppleyuan.com/)搞过一次ACM专题训练,训练题全部来至HDOJ,当时我是由易到难,每天选择一个专题,在HDOJ上找3~4题,然后在论坛给出题目,大家可以到HDOJ去提交,然后贴到论坛供其他朋友参考。板块是:http://www.cppleyuan.com/forumdisplay.php?fid=40,前面都是看书,这里就建议大家开始实战了,在论坛里一共除了200多题,大家一定要做!
4.有了一定的基础,就可以再一边进行深入(看书),一边做题了。这个时候神马《算法导论》,《计算机程序设计艺术》等等都可以看看。
5.到了这个阶段,没啥说的了,自由学习~~~

最后说一句:算法魅力,无与伦比,欢迎大家来到ACM的世界!加油!

(作者:Tanky Woo, 个人博客:http://www.wutianqi.com ,C++/算法论坛:http://www.cppleyuan.com/ 。转载请注明个人及原文连接,谢谢合作)

最短路径算法—SPFA(Shortest Path Faster Algorithm)算法分析与实现(C/C++)

建议看SPFA前先看看Dijkstra和Bellman-Ford这两个最短路算法。

SPFA的思路比较简单,网上的说法也比较统一,NOCOW和百度百科上都有。这里在网上找到讲的比较通俗易懂的:

SPFA(Shortest Path Faster Algorithm)
是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素,
并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。

它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。

SPFA 在形式上和BFS非常类似,不同的是BFS中一个点出了队列就不可能重新进入队列,但是SPFA中
一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本
身被改进,于是再次用来改进其它的点,这样反复迭代下去。

判断有无负环:如果某个点进入队列的次数超过V次则存在负环(SPFA无法处理带负环的图)。

SPFA算法有两个优化算法 SLF 和 LLL:
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,
否则插入队尾。
LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入
到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。
引用网上资料,SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。
在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。

其他最短路算法:

更多算法可以去看看我的算法专题:

http://www.wutianqi.com/sfzt.html

以下是SPFA的代码模板:

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
28
29
30
31
32
33
34
35
36
37
38
const int INF = 999999;
int  map[MAXN][MAXN]; //map[i,j]为初始输入的i到j的距离,未知的map[i,j]=INF;
int  dis[MAXN];
char vst[MAXN];
// 参数n表示结点数,s表示源点
int SPFA(int n, int s)
{
	// pri是队列头结点,end是队列尾结点
    int i, pri, end, p, t;
    memset(vst, 0, sizeof(vst));
    for(int i=0; i<MAXN; ++i)
        Q[i] = 0;
    for (i=0; i<n; i++)
        dis[i] = INF;
    dis[s] = 0;
    vst[s] = 1;
    Q[0] = s; pri = 0; end = 1;
    while (pri < end)
    {
        p = Q[pri];
        for (i=0; i<n; ++i)
        {
			//更新dis
            if (dis[p]+map[p][i] < dis[i])
            {
                dis[i] = dis[p]+map[p][i];
                if (!vst[i])     //未在队列中
                {
                    Q[end++] = i;
                    vst[i] = 1;
                }
            }
        }
        vst[p] = 0;   // 置出队的点为未标记
        pri++;
    }
    return 1;
}

HDU 1874可以用SPFA试试: