图论模板

1.带路径优化的并查集模板:

int Find(int x)
{
  int r=x;
  while(r!=pre[r])
    r=pre[r]; 
  int i=x,j;
  while(pre[i]!=r)//路径优化
  {
    j=pre[i];
    pre[i]=r;
    i=j;
  }
  return r;
}
void mix(int x,int y)
{
  int fx=Find(x),fy=Find(y);
  if(fx!=fy)
  {
    pre[fy]=fx;
  }
}

简化版 

int find(int x){
    return (x == pre[x] ? x : pre[x] = find(pre[x])); 
}

应用题目链接:
HDU P1232 畅享工程
ZOJ Problem Set – 3321 Circle


2.Floyed模板:

void floyd()
{
    int i,j,k;
    for (k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                Map[i][j]=min( Map[i][j],Map[i][k]+Map[k][j] );

}

 

HDU P1232 畅通工程(并查集)

Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? 继续阅读HDU P1232 畅通工程(并查集)

勿躁

  汝有田舍翁,家资殷盛,而累世不识“之”“乎”。一岁,聘楚士训其子,楚士始训之搦管临朱,书一画,训曰“一”字;书二画,训曰“二”字;书三画,训曰“三”字。其子辄欣欣然,掷笔归告其父曰:“儿得矣,儿得矣;可无烦先生矣,重费馆谷也,请谢去。”其父喜,从之,具币谢遣楚士。
  逾时,其父拟征召姻友万氏姓者饮,令子晨起治状,久之不成,父趣之。其子恚曰:“天下姓字伙矣,奈何姓万,自晨至今,才完五百画也。”
  初机士偶一解,而即以訑訑自矜有得。殆类是已。

应谐录》刘元卿

SDAU训练日志第44篇(2018年11月11日)

  今天是双十一,东西没买狗粮倒是被强制吃了不少。
这个月算法导论图论部分5章看完了三章多点,最短路生成树之类的原理都懂了,但是因为书上给的是伪代码,还要找时间自己不看书只靠原理实现一遍,另外还要准备一些图论的模板,毕竟学习是学习,比赛是比赛。另外网络流那一部分还没来得及看,等明天考完试就补上。
因为书是在IPAD上看的,批注都在那上边,也不能和郭忠浩那样很方便的整理下来,看看以后能不能导出批注吧。
现在平衡好了ACM和学习的关系,每天能拿出来一个半小时学习算法,平衡把握的比以前好多了。不过我更担心我的四级,那个还是一直没啥头绪,说不定要裸考了。
学习算法要戒骄戒躁,把一个寓言故事放在置顶文章上了,每天都能看见,做学问不能浅尝辄止。