首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

26/七/2012 ICPC培训 第十一天

2013-11-08 
26/7/2012ICPC培训第十一天又来喽汇报下今天吧上午就写了个强连通算法,tarjan算法,其实还是不太理解的,就

26/7/2012 ICPC培训 第十一天

又来喽26/七/2012  ICPC培训  第十一天

汇报下今天吧

上午就写了个强连通算法,tarjan算法,其实还是不太理解的,就是按葫芦画瓢。。。

刷了HDU上的一强连通模板题1269,就是判断有向图是否是连通的,也就是判断连通分量是否

只有一个。

代码:

#include<iostream>#include<vector>#include<cstring>using namespace std;const int maxn=10001;bool inStack[maxn];  //判断是否在栈中 int dfn[maxn];     //dfn表示深度遍历时的访问次序 int low[maxn];     //low表示可以回到的最小次序处int stap[maxn];   //存储遍历过的点,便于在找到强连通分量是输出 int numBuild,numRoad,numAdj,index,stop;  //房间数、路数、连通分量数、访问次序、控制输出的量 vector<int> myV[maxn];   //存储有向图 void storeMap(){    for(int j=0;j<maxn;j++)    {        myV[j].clear();    }        int from,to;    for(int i=0;i<numRoad;i++)    {        scanf("%d%d",&from,&to);        myV[from].push_back(to);    }}void tarjan(int i)  //tarjan算法 {    int j;        dfn[i]=low[i]=++index;  //深度遍历的访问次序     inStack[i]=true;        //访问到就相当于进栈     stap[++stop]=i;         //利用stap[]记录栈中的点,当找到连通分量时输出和删除         for(int k=0;k<myV[i].size();k++)   //一点一点的向下深度遍历     {        j=myV[i][k];   //取出当前和i相邻的点j                 if(!dfn[j])    //j没被访问过才访问,否则会重复求解连通分量         {            tarjan(j);                        low[i]=(low[i]>low[j])?low[j]:low[i];        }        else if(inStack[j] && dfn[j]<low[i])        {            low[i]=dfn[j];        }     }        if(dfn[i]==low[i])    {        numAdj++;                do        {            j=stap[stop--];            inStack[j]=false;        }while(i!=j);    }}      void solve(){    //初始化条件     memset(dfn,0,sizeof(dfn));    memset(inStack,false,sizeof(inStack));    numAdj=index=stop=0;        for(int i=1;i<=numBuild;i++)   //从所有点出发找连通分量     {        if(!dfn[i])   //点i之前没出现过,否则就会重复找         {            tarjan(i);        }    }}        int main(){    while(scanf("%d%d",&numBuild,&numRoad)==2,numBuild||numRoad)    {        storeMap();                solve();                if(numAdj==1) printf("Yes\n");        else printf("No\n");    }        system("pause");    return 0;}

 

然后就结束了,这两天都觉得挺累的,不太想做题。。。26/七/2012  ICPC培训  第十一天

中午回到宿舍睡觉,一脚醒来那个头痛得没话说,这天气实在伤不起。当然,这不是在为自己

不努力找借口滴。

下午比赛我居然还聊了20分钟QQ才发现比赛开始了。。。26/七/2012  ICPC培训  第十一天

介个,伤不起!

比赛共六题。都是关于图论的。并查集、强连通分量、最短路径、最小生成树。

题目出的还是很不错的。只不过这次不是像以往那样了,这次的比赛是挂在某个OJ上的。

说说我的情况吧。

共刷出来两题。呵呵,和我设想的AK还有不断一段距离。有点不爽!

但就像别人说的那样:相信努力就会有好的结果,最好的结果就是那个过程了。

我喜欢coding、喜欢学习算法,虽然有的时候会很累。但当题目AC、算法弄懂、代码运行正确、

掩藏很深的bug浮出水面时一切都是值得的了。

我还在coding的路上。。。

 

最后,我还想说的是。

代码是用来理解和掌握的,不是事先把模板准备好,比赛的时候拿过来看看就行的。这样你反而

不能从整体上分析你要解决的问题。只是一点点地修改模板,这里改好了,哪里又出问题了!

还有就是上次博客说,并查集、最小生成树、最短路。。。套路很强!

事实证明我夜郎自大了。。。

 

希望所有喜爱coding的人能过克服重重困难,心往code。

晚安。26/七/2012  ICPC培训  第十一天

 

 

 


 

 

热点排行