破除畏”难“心
图论
一直一个令我头疼的问题，不敢去做不敢去想，甚至有点畏惧。最早，一直有一个问题萦绕在心头
对书上的给的邻接表、邻接矩阵两种表示方法，感觉很构造起来麻烦，操作不方便。后来发现其实是自己菜，写的不够熟练而已。碰到图相关的问题，都是三十六计走为上策。
在 OJ
练习了一些最小生成树、并查集相关问题的后，发现困难也并不是想象中的那么大。解题时，并不是呆板的先用邻接矩阵或邻接表先把图构造完，再去跑算法。比如说hdu 1232 畅通工程这个问题，就可以用并查集给搞掉，边读取输入边跑并查集算法。
并查集的代码短小精悍，没想到图相关的问题居然可以有如此优美的解法。
1
2
3
4
5
6
7
8
9
| int root(int n)
{
if(pararent[n] == 0)
{
return n;
} else {
return pararent[n] = root(pararent[n]);
}
}
|
在中科大朱明的公开课《数据结构及算法应用》最短路一节，有一句话太精辟了
畏难心、对陌生事务的恐惧心其实完全没有必要，为之则难者亦易矣
。
不停的练习
最小生成树
在破除了自己的畏难心理之后，就开始一直坐最小生成树的练习题，是越做越有精神，越做越感觉信心越大，接连过了所有的练习最小生成树的练习提。发现kruskal算法其实还挺简单就能实现的，因为我调用了qsort函数，显得代码就简洁了不少：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int kruskal(int N){
int a_root,b_root;
int sum = 0;
for(int i = 0; i < N;++i){
a_root = root(input[i].a);
b_root = root(input[i].b);
if( a_root != b_root){
if (a_root < b_root)
{
parent[b_root] = a_root;
}else{
parent[a_root] = b_root
}
sum += input[i].cost;
}
}
return sum;
}
|
这是解决hdu 1836的一个代码片段。
代码写的多了就发现代码其实并不是每一次都要重写一遍，是可以复用的。以前只是听说代码复用，但每到做题的时候自己都是从头开始写代码。直到最近做练习题时，都是把上面的代码稍微改改，就水过了。
心旷神怡，哈哈～
最短路
做完最小生成树，就开始做最短路，虽然说他们挺像的，都用贪心算法来解的，理解的思路也感觉没什么问题，但是题，就是死活都过不去，都是处理的细节上有错误，有的是用贪心算法实现
的过程有问题，代码写的异常庞大。。最先过去hdu2544
那道水题的代码是下面的代码：
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
| #include <stdio.h>
#include <string.h>
int Graph[110][110];
int parent[110];
int dist[110];
int visited[110],visited_top;
int root(int n){
if(parent[n] == 0) return n;
else parent[n] = root(parent[n]);
}
void dijk(int N){
int a_root,b_root;
int sum = 0x7f7f7f7f;
int source,next_sourc,next_sourc_root,source_root;
while(visited_top != N){
sum = 0x7f7f7f7f;
for(int i = 0; i < visited_top; ++i){
source = visited[i];
for(int j = 1; j <= N;++j){
if(Graph[source][j]&& source!= j){
a_root = root(source);
b_root = root(j);
if(a_root == b_root){
Graph[source][j] = 0;
Graph[j][source] = 0;
continue;
}
if(dist[j] > dist[source] + Graph[source][j]){
dist[j] = dist[source] + Graph[source][j];
}
if(sum > dist[source] + Graph[source][j]){
sum = dist[source] + Graph[source][j];
next_sourc = j;
next_sourc_root = b_root;
source_root = a_root;
}
}
}
}
visited[visited_top ++] = next_sourc;
next_sourc_root > source_root?parent[next_sourc_root] = source_root:parent[source_root] = next_sourc_root;
}
}
int main(int argc, char *argv[])
{
int M,N,x,y,weight;
while(scanf("%d%d",&N,&M),N||M){
memset(Graph,0,sizeof(Graph));
memset(parent,0,sizeof(parent));
memset(visited,0,sizeof(visited));
for(int i = 0;i < M; ++i){
scanf("%d%d%d",&x,&y,&weight);
Graph[x][y] = weight;
Graph[y][x] = weight;
}
visited_top = 1;
visited[0] = 1;
for(int i = 2;i <= N;++i){
dist[i] = 0x7f7f7f7f;
}
dist[1] = 0;
dijk(N);
printf("%d\n",dist[N]);
}
return 0;
}
|
虽然过了这道水题，但是回头再一看，我自己写的这是什么，我的思路是什么呢？我完全理解不了我在怎么想的，为什么能过？
弄斧到班门
后来接着看书，看朱明教授讲的
dijkstra，听过去以后就明白了怎么回事。然后就按照其讲的过程实现了，提交上去直接就A掉了hdu 2544，思路还非常的清晰。果然自学和有个高手指点指点或者和别人讨论讨论效果不一样哇。
学到的其他一些技巧
scanf 读取输入
当年什么读到文件结尾结束；就是愣是看不明白不理解该怎么写程序让其读到文件结尾结束。后来大神指点了一下，用
1
| while(~scanf("%d%d",N,M)){}
|
一下把问题解决了，效率还挺好。处理所有的文件输入问题都基本上能用其解决。比如有一些变种：M,N
同时为零结束，就成了：
1
| while(scanf("%d%d",N,M)，N||M){}
|
还学会了scanf("%d%d%*c"，M,N);这种的读取输入数据，并且忽略一个字符（解决hdu
1301 Jungle Roads poj这道题用到的）。
文件流重定向
有的时候输入数据太累可以用读取文件的方式，在本地先建一个文本文件，输入数据，测试程序，而不用没测试一次程序都要在cmd里面输入：
1
2
| FILE *fp;
fp = freopen("in1.txt","r",stdin);
|
当然不要忘记关闭文件哦：
我为了省事从没写过这句话，还有一种方式就是用cmd进到当前文件夹下,用管道组装命令
程序名称 <保存数据的文件 >结果输出到的文件名
例如：
1
| test.ext <in.txt >out.txt
|
先说这么多吧，过去的一年学到的东西真的很多，很充实满足。
