一点学习心得。

图论里面的东西从一开始对我来说就是一个大头疼的问题，不敢去做不敢去想，甚至有点畏惧，我刚开始的时候在想，土改怎么保存比较好呢？看了书上的给的邻接表，和邻接矩阵两种方法后感觉好麻烦，操作感觉也很不爽，所以一直以来就看到图的问题，我都是三十六计走为上策。

但是当我做了一些最小生成树的问题的时候，我就开始感觉图并不是想象中的那么难，那么麻烦，并不是想象中的那样，所有的题都要用邻接矩阵或者邻接表先把输入的边什么的保存起来，然后进行操作，那简直就是太麻烦了，有些题直接就可以用并查集给搞掉，比如说hdu 1232 畅通工程这个问题，直接就变输入边用并查集给解决了。然后就发现原来图也可以如此如此简单的解决啊、呵呵。尤其是那段并查集的代码简直是太优美了，短小精悍（抄的大神的，不是原创）：

int  root(int n){  
    if(pararent[n] == 0)return n;  
    else return pararent[n] = root(pararent[n]);  
}  

后来看中科大朱明教授的数据结构及算法应用的最短路的那一节的时候，发现他说的一句话太精辟了管事的算法都不复杂，复杂的算法管不了大事。其实图中的算法与代码并不是想象中的那么难。

在破除了自己的畏难心理之后，就开始一直坐最小生成树的练习题，是越做越有精神，越做越感觉信心越大，接连过了所有的练习最小生成树的练习提。发现kruskal算法其实还挺简单就能实现的，因为我调用了qsort函数，显得代码就简洁了不少：

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){  
                a_root < b_root?parent[b_root] = a_root:parent[a_root] = b_root;  
                sum += input[i].cost;  
            }  
    }   
    return sum;  
}  

这是做hdu 1836里面的一段代码。

发现代码其实并不是每一次都要重写一遍，是可以复用的，尴尬，以前只是听说代码复用什么的，但是每到做题的时候自己都是从头开始写代码。在做的所有的练习题里面，都是把上面的代码稍微改改，就都过了。真是感觉良好呀，哈哈、、、

做完最小生成树，就开始做最短路，虽然说他们挺像的，都用贪心算法来解的，理解的思路也感觉没什么问题，但是题，就是死活都过不去，都是处理的细节上有错误，有的是用贪心算法实现 的过程有问题，代码写的异常庞大。。最先过去hdu2544 那道水题的代码是下面的代码：

#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[])
{
    //FILE *fp;    
    //fp = freopen("in.txt","r",stdin);
    
    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;
}

虽然过了这道水题，但是回头再一看，我的Maya这是什么，我的思路是什么呢？完全理解不了我在怎么想的，为什么能过呢？

后来接着看书看朱明教授讲的dijkstra，听过去以后就明白了怎么回事，然后就按照其讲的过程实现了，提交上去直接就A掉了hdu2544。 感觉思路还非常的清晰，果然自学和有个高手指点指点或者和别人讨论讨论效果不一样哇，比如说有一些细节的问题：

当年什么读到文件结尾结束；就是愣是看不明白不理解该怎么写程序让其读到文件结尾结束。后来大神指点了一下，用

while(~scanf("%d%d",N,M)){}

一下解决效率还挺好,处理所有的文件输入问题都基本上能用其解决了。有一些变种如什么M,N 同时为零结束，就成了：

while(scanf("%d%d",N,M)，N||M){}

还学会了scanf("%d%d%*c"，M,N);这种的读取输入数据，并且忽略一个字符（解决hdu

1301 Jungle Roads poj这道题用到的）。

有的时候输入数据太累可以用读取文件的方式，在本地先建一个文本文件，输入数据，测试程序，而不用没测试一次程序都要在cmd里面输入：

FILE *fp;   
fp = freopen("in1.txt","r",stdin); 

当然不要忘记关闭文件哦：

fclose(fp);

我为了省事从没写过这句话，还有一种方式就是用cmd进到但钱文件夹下,用命令

程序名称 < 保存数据的文件 >结果输出到的文件名例如：

test.ext <in.txt >out.txt

先说这么多吧，过去的一年学到的东西真的很多，很充实满足。