【CodeForces 977D】 Divide by three, multiply by two
一道比较简单的拓扑排序题(虽然需要一点数学证明)
【洛谷 P3385】 【模板】负环
Bellman-Ford 判环
【洛谷 P6101】 出言不逊
数据坑人但的确很简单的贪心
【笔记】图论-拓扑排序
一种非常简单易懂的图论算法
【笔记】图论-Tarjan 算法
一种用来求强连通分量的有趣的算法
【洛谷 P6014】 斗牛
需要一点思维的贪心
【笔记】图论-最短路径算法
在图论中,有一类算法,是专门拿来算两点之间最短距离的,被称之为最短路算法。
一共有四种最短路算法,分别是:Floyd,Dijkstra,Bellman-Ford 和 SPFA,它们时间复杂度各不相同,同时也具有各自的缺陷,今天就来介绍一下这四种算法。
参考题目:P1744 采购特价商品(四种算法参考代码均为这道题)
PS:因为图论刚起步,所以为了熟悉一下,代码都是用的链式前向星存图,其实这四种都有自己的方式,下面会讲到。
Floyed
Floyd 和其它三种不一样,是一种全源最短路径算法,也就是说,它能求出任意点为起点,任意点为终点的最短距离,而其它三种只能求出以某一点为起点,任意点为终点的最短距离,即单源最短路径。
Floyd 算法时间复杂度为O(n3)O(n^{3})O(n3),核心代码如下:
1234for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]) ...
【洛谷 P3958】 奶酪
非正解的并查集经典题型
回顾 2019
唉,又过去一年了,离初三毕业又近了一点了
这一年过的好悲惨啊
文化课凉凉~~,OI 也没什么太大的进展,怎么说呢,很不如意吧
PS:这是蒟蒻第一次写年终总结,所以可能有点水,请不要介意
OI 方面
总体来说今年在 OI 这块还算不错吧,参加了人生中第一次 CSP,就拿了一个不错
的成绩,J 组一等,虽然这还很微不足道,但也是算一个小小的成就吧(毕竟这样就能稳保直升了),而且通过这次比赛,也是拓宽了眼界,见到了很多巨佬,同时也学到了很多。
给一些**还未参加过 OI **的同学一些建议(纯属个人主观意见):
首先,在考试前,不要太紧张,J 组没什么难的,只要有一些基础,会模拟、简单 dp,最好是再来一点图论知识,只要不出大问题,一般一等是稳的
其次,不要觉得骗分是多么不好的行为,只要不是作弊(或卡评测姬), 没人规定不准骗分,甚至有时骗的比正解还好(比如我今年 T4 用邻接矩阵加记忆化 dfs 拿了 80pts)
还有,不要过早地给自己下定义,比如觉得自己铁定凉凉什么的,一切要等尘埃落定后才知道,我今年做 T4 时,贪心把邻接矩阵开大了一些,结果考完了又记错了,以为自己 MLE 了 ...