首页 > 其他分享 >【题单】 洛谷图论题单

【题单】 洛谷图论题单

时间:2024-04-06 15:31:43浏览次数:22  
标签:普及 NOI 省选 提高 最小 洛谷图 论题 模板 题单

这里写目录标题


updata

  • 2024.03.31 发布此文章

普及-

P1359 租用游艇
P1636 Einstein学画画(数据有误)
P1700 [USACO19OPEN] Milk Factory B
B3613 图的存储与出边的排序
B3643 图的存储
B3644 【模板】拓扑排序 / 家谱树
B3862 图的遍历(简单版)
P5318 【深基18.例3】查找文献
P6867 [COCI2019-2020#5] Politicari
P8604 [蓝桥杯 2013 国 C] 危险系数
P8605 [蓝桥杯 2013 国 AC] 网络寻路
P10109 [GESP202312 六级] 工作沟通

普及/提高-

P1194 买礼物
P1342 请柬
P1346 电车
P1396 营救
P1444 [USACO1.3] 虫洞 wormhole
P1476 休息中的小呆
P1529 [USACO2.4] 回家 Bessie Come Home
P1546 [USACO3.1] 最短网络 Agri-Net
P1576 最小花费
P1629 邮递员送信
P1656 炸铁路
P1661 扩散
P1744 采购特价商品
P1807 最长路
P1907 设计道路
P1991 无线通讯网
P2009 跑步
P2121 拆地毯
P2330 [SCOI2005] 繁忙的都市
P2661 [NOIP2015 提高组] 信息传递
P2814 家谱
P2820 局域网
P3371 【模板】单源最短路径(弱化版)
P3385 【模板】负环
B3611 【模板】传递闭包
P3905 道路重建
P3906 Geodetic集合
P3916 图的遍历
P2872 [USACO07DEC] Building Roads S
P1692 部落卫队

普及+/提高

P1027 [NOIP2001 提高组] Car 的旅行路线
P1038 [NOIP2003 提高组] 神经网络
P1073 [NOIP2009 提高组] 最优贸易
P1078 [NOIP2012 普及组] 文化之旅
P1119 灾后重建
P1144 最短路计数
P1260 工程规划
P1265 公路修建
P1300 城市街道交通费系统
P1340 兽径管理
P1363 幻象迷宫
P1462 通往奥格瑞玛的道路
P1522 [USACO2.4] 牛的旅行 Cow Tours
P1608 路径统计
P1525 [NOIP2010 提高组] 关押罪犯
P1685 游览
P2002 消息扩散
P2047 [NOI2007] 社交网络
P2136 拉近距离
P2296 [NOIP2014 提高组] 寻找道路
P2307 迷宫
P2620 虫洞
P4943 密室
P5905 【模板】全源最短路(Johnson)
P7113 [NOIP2020] 排水系统
P6722 「MCOI-01」Village 村庄

提高+/省选-

P1262 间谍网络
P1343 地震逃生
P1453 城市环路
P1730 最小密度路径
P1772 [ZJOI2006] 物流运输
P1768 天路
P1783 海滩防御
P1967 [NOIP2013 提高组] 货车运输
P1989 无向图三元环计数
P2185 公路通行税
P2245 星际导航
P2573 [SCOI2012] 滑雪
P2656 采蘑菇
P2691 逃离
P2738 [USACO4.1] 篱笆回路Fence Loops
P2812 校园网络【[USACO]Network of Schools加强版】
P3831 [SHOI2012] 回家的路
P4578 [FJOI2018] 所罗门王的宝藏

省选/NOI−

P2680 [NOIP2015 提高组] 运输计划
P2767 树的数量
P2829 大逃离
P4009 汽车加油行驶问题
P4172 [WC2006] 水管局长
P4320 道路相遇
P4321 随机漫游
P4716 【模板】最小树形图
P5633 最小度限制生成树
P6192 【模板】最小斯坦纳树
P6436 「EZEC-1」越狱
P4234 最小差值生成树
P4151 [WC2011] 最大XOR和路径
P2792 [JSOI2008] 小店购物

NOI/NOI+/CTSC

P1753 矩阵链排序问题
P2081 [NOI2012] 迷失游乐园
P4073 [WC2013] 平面图
P5180 【模板】支配树
P5247 【模板】动态图连通性
P5295 [北京省选集训2019] 图的难题
P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
P8581 [CoE R5] X 细胞
P9249 [集训队互测 2018] 完美的旅行

标签:普及,NOI,省选,提高,最小,洛谷图,论题,模板,题单
From: https://blog.csdn.net/xzz_0611/article/details/137197478

相关文章

  • 【题单】 往届 CSP/s 题目(洛谷)
    这里写目录标题updata20232022202120202019updata2023P9752[CSP-S2023]密码锁P9753[CSP-S2023]消消乐P9754[CSP-S2023]结构体P9755[CSP-S2023]种树2022P8817[CSP-S2022]假期计划P8818[CSP-S2022]策略游戏P8819[CSP-S2022]星战P8820[......
  • 洛谷题单指南-图的基本应用-P1347 排序
    原题链接:https://www.luogu.com.cn/problem/P1347题意解读:在给出多对关系字母的比较关系之后,判断能否确定所有字母的顺序。解题思路:对字母的关系建立图,如A<B建立A指向B的一条边。如果在拓扑排序过程中,每次寻找入度为0的点只有一个,且最终可以形成拓扑序,则可以确定所有字母的顺......
  • 洛谷题单指南-图的基本应用-P1363 幻象迷宫
    原题链接:题意解读:迷宫可以无限扩展,对第一个样例进行模拟,扩展4块的示意图:从起点S,沿着红色虚线,是可以无限走下去的,要判断是否能够无限走下去。解题思路:直观上,会考虑把迷宫复制多块,但是会面临2个问题:1、内存可能爆掉2、如何有效判断可以无限走下去?只考虑竖向或者横向连通是不......
  • 一些乱七八糟的题单之类的
    打算每做一道题都放到这里,因为我之前的题单被我弃用然后删了QAQ知识点肯定不全。。。我啥时候写到对应知识点再加过去,对于一些很多做法题目按照我写的是啥为准(Link-CutTree链操作/维护链上信息P4847银河英雄传说V2P1501[国家集训队]TreeIIP4332[SHOI2014]三叉神经树......
  • 洛谷题单指南-图的基本应用-P2853 [USACO06DEC] Cow Picnic S
    原题链接:https://www.luogu.com.cn/problem/P2853题意解读:找到所有奶牛都可以到达的牧场,就是要从奶牛所在位置开始遍历,求所有奶牛能重合的点的个数。解题思路:直接从从牛奶所在位置进行DFS,记录每个位置有奶牛能到的个数,个数等于奶牛总数的即合适的牧场。100分代码:#include<bi......
  • 洛谷题单指南-图的基本应用-P1127 词链
    原题链接:https://www.luogu.com.cn/problem/P1127题意解读:按字典序排列单词,使得相邻单词的首位字母一样。解题思路:由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样,因此可以遍历每一个单词,再找到每一个可以接在其后面的单词,建立一个邻接表,然后从......
  • 洛谷题单指南-图的基本应用-P1807 最长路
    原题链接:https://www.luogu.com.cn/problem/P1807题意解读:由于对于每一条边u->v,都有u<v,因此节点1的入度一定是0,且是有向无环图,直观上可以通过拓扑排序法搜索每一个节点,计算1到每一个节点的最长距离。但问题在于,入度为0的节点可能不止一个,这样在计算到某个点的最长距离时,会受到......
  • 洛谷题单指南-图的基本应用-P4017 最大食物链计数
    原题链接:https://www.luogu.com.cn/problem/P4017题意解读:食物链的顶端不会被其他生物吃,在图结构中设定为入度是0,食物链的底端不会吃其他生物,在图结构式设定为出度是0,此题就是要计算所有入度是0的点到所有出度是0的点一共有多条路径。解题思路:首先,来模拟一样样例,样例数据形成的......
  • 洛谷题单指南-图的基本应用-P3916 图的遍历
    原题链接:https://www.luogu.com.cn/problem/P3916题意解读:寻找每个点所能到达的最大的点。解题思路:直观上,可以依次从每个点开始DFS搜索,记录经过的最大点,复杂度是O(n^2)级别,会超时。可以换一种角度,既然要找每个点可以达到的最大值,那么可以反向建图,从最大值出发,所经过的点能达到......
  • 洛谷题单指南-图的基本应用-P5318 【深基18.例3】查找文献
    原题链接:https://www.luogu.com.cn/problem/P5318题意解读:图的建立、DFS、BFS模版题。解题思路:本题主要考察建图、图的DFS、BFS遍历。建图方式:领接表vector<int>g[N];需要注意的是,在DFS、BFS搜索领接点时,需要先将领接点编号排序,满足题目要求的“如果有很多篇文章可以参阅,请......